프로그래머스 [Lv. 3] 경주로 건설 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

function solution(board) {
    const n = board.length;
    const [er, ec] = [n-1, n-1];
    const maxCosts = 25 * 25 * 500 + 1;
    let visited = Array(n).fill().map(() => Array(n).fill().map(() => Array(4).fill().map(() => maxCosts)));
    
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < n;
    };
    
    // 방향, 금액, r, c
    // 아래로 시작, 오른쪽으로 시작
    let q = [[1, 0, 0, 0], [3, 0, 0, 0]]
    while (q.length) {
        const [direction, cost, r, c] = q.shift();
        for (let d = 0; d < 4; d++) {
            const nr = r + dr[d];
            const nc = c + dc[d];
            if (isValid(nr, nc) && board[nr][nc] == 0) {
                const newCosts = cost + (direction == d ? 100 : 600);
                if (newCosts < visited[nr][nc][direction]) {
                    visited[nr][nc][direction] = newCosts;
                    q.push([d, newCosts, nr, nc]);
                };
            };
        };
        q.sort(([a, b, c, d], [e, f, g, h]) => b - f);
    };
    
    const answer = Math.min(...visited[er][ec]);
    return answer;
}

풀이 방법

1. n * n * 4인 3차원 배열을 만든다.
   1. 비용이 작은 길이를 찾기 위해 maxCost 값으로 채운다.
   2. 적당히 큰 크기로 n이 25가 최대이기 때문에 25 * 25에 500을 곱하고 1을 더했다.
   3. 더 정확하려면 25 * 25 * 600 + 1이 맞을 것 같다.
2. 시작 지점은 0,0이며 방향을 아래, 오른쪽으로 설정했다. (당연한 얘기다)
3. 현재 지점에서 다음 지점으로 이동할 때 방향이 바뀌면 코너가 생기므로 600을 더한다.
   1. 아닌 경우는 100을 더한다.
   2. 여기서 600을 더하는 이유는 직선 도로 하나 + 코너 하나가 생기기 때문이다.
4. 4방향 탐색이 끝나면 q를 정렬한다.
   1. 람다식을 사용해서 현재 든 비용을 기준으로 오름차순 정렬한다.
   2. 가장 적게 든 비용부터 움직이기 위함이다.
5. 이후 도착지점의 배열에서 최값을 구한 뒤 answer에 대입하면 끝!

느낀점

• 사실 이 문제는 heapq로 푸는게 정배?인데 굳이 없어도 풀린다.
• bfs라고 했지만 dp에 가까운 것 같기도 하다.
• 요즘 다시 풀어 봐야 하는 문제들이 많아진다.
• 한 번 복습할 필요가 있다.