[Programmers] 경주로 건설 문제 - (javascript)

문제 이름 :  경주로 건설

---

 

<<< 문제 내용 >>>

https://programmers.co.kr/learn/courses/30/lessons/67259#

문제가 굉장히 길어 링크를 첨부합니다.

---

 

function solution(board) {
  let boardLen = board.length;

  const dy = [-1, 1, 0, 0];
  const dx = [0, 0, -1, 1];

  const bfs = (y, x, dir, money) => {
    let queue = [[y, x, dir, money]];

    while (queue.length > 0) {
      [y, x, dir, money] = queue.shift();

      for (let i = 0; i < 4; i++) {
        const nY = y + dy[i];
        const nX = x + dx[i];

        if (
          nY < 0 ||
          nY >= boardLen ||
          nX < 0 ||
          nX >= boardLen ||
          board[nY][nX] === 1
        )
          continue;

        const bill = dir === i ? money + 100 : money + 600;
        if (board[nY][nX] === 0 || board[nY][nX] >= bill) {
          board[nY][nX] = bill;
          queue.push([nY, nX, i, bill]);
        }
      }
    }

    return board[boardLen - 1][boardLen - 1] - 500;
  };

  return bfs(0, 0, -1, 0);
}

* 이 코드는 테스트 케이스 25번을 통과하지 못합니다.

 

반례를 찾아본 결과 동일지점에서 하나는 방향을 바꿔서, 하나는 직진으로 왔을 때

값이 더 작은 것을 넣으면, 그 다음 위치에서는 오히려 값이 컸던게 더 작은 값을 가지는 경우가 있습니다.

 

이 부분을 개선하지 못했습니다.. 3차원 배열을 이용하여 해결하는 것 같았는데

이해가 되지 않아 추후 수정해 볼 예정입니다.

 

이 코드를 올린 이유는 혹시나 테스트 케이스 25번이 무엇인가 하는 분들을 위해 작성하였습니다.

 

 

 

도움이 되셨다면 공감 부탁드립니다.