[프로그래머스] 카카오 - 경주로 건설

문제

2020 카카오 인턴십 - 경주로 건설

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

 

 

풀이

설명

경주로를 건설하는데 필요한 최소 비용을 구하는 문제입니다.

 

다익스트라 알고리즘을 사용해 해결할 수 있습니다.

 

이 문제에서 다익스트라 알고리즘을 사용할 때 주의해야 할 부분은 다음과 같습니다.

어떤 지점 C를 거쳐서 바로 오른쪽인 D로 가는 루트가 2개 있다고 하겠습니다. 1번 루트는 C의 위쪽인 A에서 C로 도착하기까지 2100원의 비용이 들고, 2번 루트는 C의 왼쪽인 B에서 C로 도착하기까지 2500원이 들었습니다. 1번 루트를 통해 D까지 간다면 코너를 하나 추가해야 하므로 총 2700원이 들지만, 2번 루트를 통한다면 코너를 추가할 필요가 없어 총 2600원이 들게 됩니다. 즉, C까지 드는 비용은 1번 루트가 더 적지만, D까지 드는 비용은 2번 루트가 더 적게 됩니다.

 

따라서 무조건 새 비용이 기존 비용보다 높다고 해당 탐색을 스킵하는 것이 아니라, 기존 비용에 코너 비용을 추가했을 때보다 크거나 같게 되었을 때 스킵하게 만들어야 합니다.

 

예시 코드

function solution(board) {
  const ROAD_COST = 100;
  const CORNER_COST = 500;

  const n = board.length;
  const cost = Array.from({ length: n }, () => Array(n).fill(Infinity));
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  const queue = new PriorityQueue();
  queue.enqueue([0, 0, 0, -1], 0);

  cost[0][0] = 0;

  while (!queue.isEmpty()) {
    const [currCost, x, y, dir] = queue.dequeue().value;

    for (let i = 0; i < directions.length; i++) {
      const [dx, dy] = directions[i];
      const nx = x + dx;
      const ny = y + dy;

      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      if (board[nx][ny] === 1) continue;

      let newCost = currCost + ROAD_COST;
      if (dir !== -1 && dir !== i) newCost += CORNER_COST;

      if (newCost >= cost[nx][ny] + CORNER_COST) continue;
      cost[nx][ny] = Math.min(cost[nx][ny], newCost);
      queue.enqueue([newCost, nx, ny, i], newCost);
    }
  }

  return cost[n - 1][n - 1];
}