프로그래머스 LEVEL 3(경주로 건설)

사용 언어 : javascript
해결 날짜 : 2023-04-17
해결 방법 :
- dfs를 활용해 문제 해결
  - 현재 위치가 board의 마지막 열 마지막 행에 도착했을 때 answer 작은 값으로 업데이트 후 종료
  - 현재 위치에서 상, 하, 좌, 우를 살피며 이동 가능할 때
    - 직선 도로라면 cost에 100, 코너라면 600 추가
    - 이 때 다음 방향으로 이동했을 때 cost와 dp를 비교하여 작은 값으로 업데이트 후 재귀

회고 :

최단 경로를 찾는 문제이긴 하지만 경로의 특징을 저장해야 하므로 bfs보다는 dfs로 푸는게 맞을 것이라 생각했다.

dfs로 처음에 짠 코드

function solution(board) {
  let answer = Infinity;

  const maxSize = board.length - 1;
  const moves = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];

  const dfs = (prevPos, pos, cost) => {
    const [x, y] = pos;

    if (x === maxSize && y === maxSize) {
      answer = Math.min(answer, cost);
      return;
    }

    board[x][y] = 1;
    moves.forEach((move) => {
      const nextX = x + move[0],
        nextY = y + move[1];

      if (nextX < 0 || nextX > maxSize || nextY < 0 || nextY > maxSize || board[nextX][nextY])
        return;

      let addingCost = 100;

      if (prevPos) {
        const [prevX, prevY] = prevPos;

        addingCost = Math.abs(nextY - prevY) === 2 || Math.abs(nextX - prevX) === 2 ? 100 : 600;
      }

      dfs([x, y], [nextX, nextY], cost + addingCost);
    });

    board[x][y] = 0;
  };

  dfs(undefined, [0, 0], 0);

  return answer;
}

테스트 케이스는 바로 통과했지만, 제출했을 때 절반 정도에서 시간 초과 문제가 발생했다…

dp를 통해 최적화가 필요함을 알게 되었고, 다음과 같이 작성했다.

function solution(board) {
  let answer = Infinity;

  const maxSize = board.length - 1;
  const moves = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const dp = Array.from({ length: maxSize + 1 }, () =>
    Array.from({ length: maxSize + 1 }, () => Infinity),
  );

  const dfs = (prevPos, pos, cost) => {
    const [x, y] = pos;

    if (x === maxSize && y === maxSize) {
      answer = Math.min(answer, cost);
      return;
    }

    board[x][y] = 1;
    moves.forEach((move) => {
      const [nextX, nextY] = [x + move[0], y + move[1]];

      if (nextX < 0 || nextX > maxSize || nextY < 0 || nextY > maxSize || board[nextX][nextY])
        return;

      let addingCost = 100;

      if (prevPos) {
        const [prevX, prevY] = prevPos;

        addingCost = Math.abs(nextY - prevY) === 2 || Math.abs(nextX - prevX) === 2 ? 100 : 600;
      }

      if (cost + addingCost > dp[nextX][nextY]) {
        return;
      }

      dp[nextX][nextY] = cost + addingCost;
      dfs([x, y], [nextX, nextY], cost + addingCost);
    });

    board[x][y] = 0;
  };

  dfs(undefined, [0, 0], 0);

  return answer;
}

시간 초과 문제는 해결했지만, 아직 테스트 케이스 두 개가 통과하지 못했다..
도저히 원인을 찾지 못하겠어서 힌트를 참고했는데, dfs의 방문 순서를 변경해주면 된다는 답변을 보고 변경했더니 다 통과했다. 왜지..? 이유 아시는 분 알려주세요 ㅠ
```
// const moves = [[1, 0], [0, 1], [-1, 0], [0, -1]];
const moves = [
  [0, 1],
  [1, 0],
  [-1, 0],
  [0, -1],
];
```

코드

function solution(board) {
  let answer = Infinity;

  const maxSize = board.length - 1;
  const moves = [
    [0, 1],
    [1, 0],
    [-1, 0],
    [0, -1],
  ];
  const dp = Array.from({ length: maxSize + 1 }, () =>
    Array.from({ length: maxSize + 1 }, () => Infinity),
  );

  const dfs = (prevPos, pos, cost) => {
    const [x, y] = pos;

    if (x === maxSize && y === maxSize) {
      answer = Math.min(answer, cost);
      return;
    }

    board[x][y] = 1;
    moves.forEach((move) => {
      const [nextX, nextY] = [x + move[0], y + move[1]];

      if (nextX < 0 || nextX > maxSize || nextY < 0 || nextY > maxSize || board[nextX][nextY])
        return;

      let addingCost = 100;

      if (prevPos) {
        const [prevX, prevY] = prevPos;

        addingCost = Math.abs(nextY - prevY) === 2 || Math.abs(nextX - prevX) === 2 ? 100 : 600;
      }

      if (cost + addingCost > dp[nextX][nextY]) {
        return;
      }

      dp[nextX][nextY] = cost + addingCost;
      dfs([x, y], [nextX, nextY], cost + addingCost);
    });

    board[x][y] = 0;
  };

  dfs(undefined, [0, 0], 0);

  return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges