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

문제 링크

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

문제

링크 참조

제한사항

링크 참조

알고리즘: 데익스트라

풀이

이 문제는 (0,0) 에서 (N-1,N-1)까지 경주로를 건설하는 데 필요한 최소 비용을 구하는 문제다. 시작점에서 (N-1,N-1)까지 가는데 최소 비용이기 때문에 데익스트라 알고리즘이 적합하다.
여기서 중요한 점은 좌표로만 정점을 구분해서는 안된다. 좌표 + 방향으로 정점을 구분해야 한다.
왜냐하면
0 0 v
0 >(1,2) => (1,2)까지 도로를 건설할 때 하 방향으로 건설했을 때와 우 방향으로 건설했을 때 단순히 비용으로만 갱신한다면 문제가 발생한다.
어떤 문제냐? 하 방향으로 이어진 (1,2)에서 우 방향으로 도로를 건설하기 위해서는 코너를 만들어야 한다. 하지만 우 방향으로 이어진 (1,2)에서 우 방향으로 도로를 건설하기 위해서는 직선 도로만 만들면 된다.
ex)-> (1,2)가 400이고 v (1,2)가 300일 때 비용만 가지고 갱신하면 v (1,2)로 갱신되고 v (1,2) -> (1,3)은 900이 됨 하지만 -> (1,2) -> (1,3)은 500임.

즉, 결론은 좌표 + 방향까지 고려해서 최소 비용 테이블(dp)을 갱신해 줘야하는 게 이 문제의 핵심이다.

소스 코드

import java.util.*;
class Node implements Comparable<Node> {
    int x, y, w, dir;
    Node(int x, int y, int w, int dir) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.dir = dir;
    }
    public int compareTo(Node o) {
        return this.w - o.w;
    }
}
class Solution {
    static final int[] dx = {-1, 0, 1, 0}; //좌 상 우 하
    static final int[] dy = {0, -1, 0, 1};
    static int H, W;
    static int[][][] dp;
    static boolean[][][] visited;
    public int solution(int[][] board) {
        int answer = 0;
        H = board.length;
        W = board[0].length;
        dp = new int[H][W][4];
        visited = new boolean[H][W][4];
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) Arrays.fill(dp[i][j], Integer.MAX_VALUE);
        }
        dijkstra(board);
        return Math.min(dp[H-1][W-1][2], dp[H-1][W-1][3]);
    }

    static void dijkstra(int[][] board) {
        PriorityQueue<Node> pque = new PriorityQueue<>();
        dp[0][0][2] = 0;
        dp[0][0][3] = 0;
        pque.add(new Node(0, 0, 0, 2)); //우
        pque.add(new Node(0, 0, 0, 3)); //하
        while(!pque.isEmpty()) {
            Node n = pque.poll();
            if(visited[n.y][n.x][n.dir]) continue;
            visited[n.y][n.x][n.dir] = true;
            for(int i=0; i<4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if((0<=nx && nx<=W-1) && (0<=ny && ny<=H-1)) {
                    if(board[ny][nx] == 0) {
                        int next_w = n.w;
                        if(n.dir == 0 || n.dir == 2) {
                            //좌우로 진행중 일 때
                            if(i == 0 || i == 2) next_w += 100; //직선
                            else next_w += 600; //코너
                        } else if(n.dir == 1 || n.dir == 3){
                            //상하면 진행중 일 때
                            if(i == 0 || i == 2) next_w += 600; //코너
                            else next_w += 100; //직선
                        }
                        if(dp[ny][nx][i] > next_w) {
                            dp[ny][nx][i] = next_w;
                            pque.add(new Node(nx, ny, next_w, i));
                        }
                    }
                }
            }
        }
    }
}