[다익스트라] 프로그래머스 - 경주로 건설 (JAVA)

문제

N x N 보드에서 (0, 0)부터 (N-1, N-1)까지 도로를 건설하는 최소 비용을 구합니다.

• 빈 칸 0, 벽 1이며 벽은 지날 수 없습니다
• 직선 도로 1개당 100원
• 코너 1개당 500원 추가

접근

비용 기준 다익스트라로 접근했습니다. 문제는 같은 칸에 더 싸게 도착해도 그때의 진입 방향이 나쁘면 이후에 500원이 더 붙어 손해가 될 수 있다는 점입니다. 비용만으로는 한 칸의 상태를 대표할 수 없습니다.

그래서 dist[n][n][4]로 (좌표, 진입 방향)을 하나의 상태로 관리하고, 출발 지점은 직전 방향이 없으므로 direction = -1로 두었습니다. 마지막에는 도착 칸의 4방향 값 중 최솟값을 고릅니다.

핵심 두 줄

다익스트라에서 실제로 중요한 부분은 nCost 계산과 그 밑의 갱신 조건문입니다. 특히 갱신 조건이 정확히 무엇을 걸러내는 조건인지 잘 몰랐습니다.

코드

import java.util.*;

class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][][] dist;
    static int n;
    static int minTotal;
    public int solution(int[][] board) {
        minTotal = Integer.MAX_VALUE;
        n = board.length;

        dijkstra(0, 0, board);

        // 도착 칸도 진입 방향별로 값이 따로 있으므로 4개 중 최솟값이 정답
        for(int i=0; i<4; i++) {
            minTotal = Math.min(minTotal, dist[n-1][n-1][i]);
        }

        return minTotal;
    }

    static void dijkstra(int x, int y, int[][] board) {
        // dist[행][열][진입 방향] = 그 상태에 도달하는 최소 비용
        dist = new int[n][n][4];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                Arrays.fill(dist[i][j], Integer.MAX_VALUE);
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 출발점은 직전 방향이 없으므로 direction을 -1로 둔다
        pq.offer(new Node(x, y, 0, -1));

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            for(int dir=0; dir<4; dir++) {
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if(board[nx][ny] == 1) continue;

                // 칸 하나를 새로 깔았으니 기본 100원
                int nCost = cur.cost + 100;
                // 직전에 온 방향(cur.direction)과 지금 가려는 방향(dir)이 다르면 코너를 튼 것이므로 500원 추가
                // cur.direction이 -1이면 출발점이라 직전 방향 자체가 없다. 첫 이동은 코너가 아니다
                if(cur.direction != -1 && dir != cur.direction) {
                    nCost += 500;
                }

                // "(nx, ny) 칸에 dir 방향으로 진입한다"는 상태의 기존 최소 비용보다 지금이 더 싼가?
                // 같은 칸이라도 진입 방향이 다르면 별개의 상태라서 dist에 dir 인덱스가 붙어 있다
                // 칸과 방향이 모두 같다면 그 이후 전개는 완전히 동일하므로, 더 비싼 쪽은 볼 필요 없이 버린다
                if(nCost < dist[nx][ny][dir]) {
                    dist[nx][ny][dir] = nCost;
                    pq.offer(new Node(nx, ny, nCost, dir));
                }
            }
        }
    }
    
    class Node implements Comparable<Node> {
        int x;
        int y;
        int cost;
        int direction;

        Node(int x, int y, int cost, int direction) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.direction = direction;
        }

        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }
}