Programmers 67259 - 경주로 건설

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

프로그래머스

 

N x N 크기의 격자 형태의 board가 존재하고 각 격자의 칸은 0 또는 1로 채워져 있으며, 0은 칸이 비어있음을 1은 해당 칸이 벽으로 채워져 있음을 나타낸다.

시작점은 (0,0) 칸(좌측 상단), 도착점은 (N-1, N-1)(우측 하단)이다.

직선 도로와 코너가 존재한다. 직선 도로는 상하 또는 좌우로 연결한 경주로를 의미하고 두 직선 도로가 직각으로 만다는 지점을 코너라고 한다.

직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 든다.

경주로를 건설하는데 들어가는 최소 비용은?

 

가중치가 존재하는 최단 거리 문제이다. 최소 비용을 구하기 위해서는 추가 금액이 들어가는 코너를 최소한으로 써야지 가능할 것 같다.

코너의 판정은 어떻게 해야 할까? 코너는 결국 이동 방향이 변경됐다는 것이다. 따라서 직전 이동 방향과 이번 이동 뱡향을 알면 코너인지를 판단할 수 있다. 즉 이전과 방향이 다르면 코너다.

좌우의 경우도 방향이 다르다. 하지만 이 경우는 코너가 아니다. 그런데 어차피 이 경우는 생각하지 않아도 된다. 최단거리를 찾는데 돌아가는 경우는 없다.

풀이를 생각해보자. 우선 가중치가 있는 최단거리를 구해야 하는 문제이다. 다익스트라로 풀 수 있을까?

다익스트라의 PriorityQueue에 넣을 때 방향도 함께 넣어서 방향별로 다른 경로로 판정하면 가능할 것 같다.

import java.util.*;

class Solution {
    
    static class Node {
        int r;
        int c;
        int dir;
        int cost;
        
        public Node(int r, int c, int dir, int cost) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.cost = cost;
        }
    }
    
    static final int INF = Integer.MAX_VALUE;
    static int[] dr = {-1, 1, 0, 0}; //상하좌우
    static int[] dc = {0, 0, -1, 1};
    
    static int[][] distances;
    
    public int solution(int[][] board) {
        int N = board.length;
        distances = new int[N][N];
        for (int[] row : distances) {
            Arrays.fill(row, INF);
        }
        
        distances[0][0] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
        pq.add(new Node(0, 0, 1, 0));
        pq.add(new Node(0, 0, 3, 0));
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int r = curr.r;
            int c = curr.c;
            int dir = curr.dir;
            int cost = curr.cost;
            
            if (distances[r][c] < cost) continue;
            
            for (int d = 0; d < 4; d++) {
                int weight = 100;
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if (board[nr][nc] == 1) continue;
                if (dir != d) {
                    weight += 500;
                }
                
                if (distances[nr][nc] > distances[r][c] + weight) {
                    distances[nr][nc] = distances[r][c] + weight;
                    pq.add(new Node(nr, nc, d, distances[nr][nc]));
                }
            }
        }
        
        int answer = distances[N-1][N-1];
        return answer;
    }
}

이렇게 풀었는데 오답이 됐다. 왜 틀렸는지 분석해 보자.

가장 큰 문제는 int [][] distances 배열이다.

나는 처음에는 직선으로 도착하거나 코너로 도착하거나 둘 중 하나이니까 그 두 경우를 전부 pq에 넣으면 어차피 저렴한 걸로 갱신되지 않을까 생각했다. 그런데 이렇게 풀게 되면 그 지점까지의 최솟값이 최종적인 최솟값이라고 보장이 돼야 한다. 하지만 이 문제는 그렇지 않다.

이렇게 관리하게 되면 같은 위치라도 다른 방향으로 도착했을 때의 비용 차이를 반영하지 못한다.

결과적으로, 특정 위치에 더 높은 비용으로 도착했지만, 방향이 달라서 이후 경로에서 더 낮은 총비용을 가질 수 있는 경우를 놓치게 되는 것이다.

이를 해결하기 위해 int [][][] distances로 3차원으로 방향까지 관리하도록 하겠다.

import java.util.*;

class Solution {
    
    static class Node {
        int r;
        int c;
        int dir;
        int cost;
        
        public Node(int r, int c, int dir, int cost) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.cost = cost;
        }
    }
    
    static final int INF = Integer.MAX_VALUE;
    static int[] dr = {-1, 1, 0, 0}; //상하좌우
    static int[] dc = {0, 0, -1, 1};
    
    static int[][][] distances;
    
    public int solution(int[][] board) {
        int N = board.length;
        distances = new int[4][N][N];
        for (int d = 0; d < 4; d++) {
            for (int[] row : distances[d]) {
                Arrays.fill(row, INF);
            }
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
        for (int d = 0; d < 4; d++) {
            distances[d][0][0] = 0;
            pq.add(new Node(0, 0, d, 0));
        }
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int r = curr.r;
            int c = curr.c;
            int dir = curr.dir;
            int cost = curr.cost;
            
            if (distances[dir][r][c] < cost) continue;
            
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                int weight = 100;
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if (board[nr][nc] == 1) continue;
                
                if (dir != d) {
                    weight += 500;
                } 
                
                if (distances[d][nr][nc] > distances[dir][r][c] + weight) {
                    distances[d][nr][nc] = distances[dir][r][c] + weight;
                    pq.add(new Node(nr, nc, d, distances[d][nr][nc]));
                }
            }
        }
        
        int answer = INF;
        for (int d = 0; d < 4; d++) {
            answer = Math.min(answer, distances[d][N-1][N-1]);
        }
        return answer;
    }
}

이를 통해 문제를 해결할 수 있었다.