(javascript) 경주로 건설

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

프로그래머스

 

다익스트라 알고리즘으로 풀 수 있었다.

다만 경주로 부지 한칸에도 4가지 경주로가 들어설 수 있기 때문에, N*N*4 만큼의 배열이 필요했다.

 

똑같은 경주로 부지라도, 상하좌우 네 방향에서 이어지는 도로가 건설 될 수 있기 때문이다.

 

먼저 부지에 건설될 도로의 비용을 기록할 cost 삼중배열을 준비한다.

cost[0][0]을 초기화해준다. cost[0][0]은 네 방향 모두에서 비용이 0이다.

 

다익스트라 알고리즘을 수행하기 위한 큐를 준비한다.

도로의 비용을 계산할 때, 이전 도로의 방향이 중요하다. 그렇기 때문에 시작 부지에 위쪽과 왼쪽 방향에서 오는 가상의 도로가 있다고 생각하고 두 경우를 queue에 넣어준다.

 

다익스트라 알고리즘을 수행한다.

queue에서 첫 요소를 꺼내온다. 요소는 x, y, d로 이루어져 있다. x, y는 부지의 좌표, d는 이전 도로의 방향이다.

 

예를 들어 [x, y, d] = [1, 0, 1]이라면, (1, 0) 위치의 부지에 1번 방향의 도로가 이어져 있다는 뜻이다.

도로의 방향은 0: 위쪽, 1: 왼쪽, 2: 아래쪽, 3: 오른쪽이다. 이는 dx, dy로 정해진다.

 

다음 칸에 지어질 도로의 비용을 계산한다. 기본 비용은 이전 부지에 있는 도로의 비용과 같다.

만약 다음 경주로의 방향이 이전 부지로 향한다면 무시한다. 경주로를 되돌아갈 필요는 없기 때문이다.

만약 다음 경주로의 방향이 이전 경주로의 방향과 일치한다면 기본 비용에 100을 더한다.

만약 다음 경주로의 방향이 이전 경주로의 방향과 다르다면 기본 비용에 600을 더한다. (도로값 + 코너값)

 

만약 다음 칸에 해당하는 방향의 도로가 없거나, 있더라도 새로운 도로의 비용이 더 싸다면 cost를 갱신한다.

cost가 갱신된 경우에는 queue에 넣어준다.

 

작업을 모두 마친 후, cost[N-1][N-1]의 네 방향의 도로 비용 중 최저값을 반환한다. 물론 -1은 제외해야한다.

 

코드

function solution(board) {
    var answer = Infinity;
    const N = board.length;
    const dx = [0, -1, 0, 1];
    const dy = [-1, 0, 1, 0];

    let cost = Array.from({ length: N }, () => Array.from({ length: N }, () => new Array(4).fill(-1)));

    let queue = [];
    for (var i = 0; i < 4; i++) {
        cost[0][0][i] = 0;
    }
    queue.push([0, 0, 0]);
    queue.push([0, 0, 1]);

    while (queue.length > 0) {
        let [x, y, d] = queue.shift();
        for (let i = 0; i < 4; i++) {
            var nx = x + dx[i];
            var ny = y + dy[i];
            var nd = (i + 2) % 4;

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

            // calculate cost
            var nc = cost[x][y][d];

            if (d === nd) nc += 100;
            else nc += 600;

            if (cost[nx][ny][nd] === -1 || nc < cost[nx][ny][nd]) {
                cost[nx][ny][nd] = nc;
                queue.push([nx, ny, nd]);
            }
        }
    }
    for (var i = 0; i < 4; i++) {
        if (cost[N - 1][N - 1][i] !== -1 && cost[N - 1][N - 1][i] < answer) answer = cost[N - 1][N - 1][i];
    }
    return answer;
}

 

 

후기

다익스트라 알고리즘으로 쉽게 풀 수 있는 문제였다. 다만 각 경주로 부지마다 네 방향의 도로를 모두 고려해야 하는 점이 헷갈리게 했다. 게다가 평범한 bfs와 다익스트라 알고리즘을 혼동하는 바람에 쓸모없는 visited배열같은걸 만들고 혼자 머리를 싸매고 있었다. 바보같다.