[다익스트라/Java] SWEA 1249. 보급로

 

SW Expert Academy

해석

이 문제는 시작 노드와 끝 노드가 정해져 있는 상태에서, 최단 거리를 구하는 문제이므로 기본적으로 BFS를 이용한 그래프 알고리즘 문제일 것이라 가정하였다.

여기서 처음에 문제를 이해할 때에는 가중치가 양수라 생각했기에 다익스트라 알고리즘이 적절할 것이라 보았다.

다익스트라는 시간복잡도가 O(ElogV)이므로 N = 100인 문제에서는 문제 없다.

--

근데 나중에 생각하니, 가중치의 범위에 대한 언급이 없어서 문제가 명확하게 조건을 제시하고 있는 것 같지는 않다. 근데 출제 의도는 다익스트라 였던 것 같다.

다익스트라 알고리즘은 특정 노드를 기준으로, 이와 연결된 모든 노드에 대하여 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 다음과 같은 조건을 갖는다.

 

1. 가중치(edge)는 양수여야 한다. (음수x)
2. 유향 그래프여야 한다.

다익스트라 알고리즘은 BFS 기반으로 구성되며, 대개의 경우 우선순위 큐(최소힙)를 이용하여 그리디하게 각 인접한 vertices 간 edge를 선정하여 최단 경로를 탐색하게 된다. 이 때, 가중치에 기반하여 더 최단 거리가 존재할 경우에는 그 거리값을 갱신한다.

풀이

인접 리스트를 운영하지 않고 2차원 배열 상에서 움직이는 문제이므로, 4방향으로 움직이는 것을 '유향'으로 해석하여 다익스트라를 적용하였다.

다익스트라는 기존에 일반적으로 구현하던 2차원 배열에서의 BFS와 달리, 과거에 그리디하게 방문했던 노드라 하더라도, 그리디한 방식이 무조건 최선이라는 보장이 없으므로 최단 거리가 나중에 발생하게 되면 이를 갱신하기 위해 visited 배열을 별도로 운영하지 않는다는 특징이 있다.

package ssafy.사전학습;  

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.PriorityQueue;  
import java.util.Queue;  

public class 보급로 {  
    private static int[][] distances;  
    private static int[][] weights;  
    private static int n;  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int t = Integer.parseInt(br.readLine());  
        for (int i = 1; i <= t; i++) {  
            n = Integer.parseInt(br.readLine());  
            weights = new int[n][n];  
            distances = new int[n][n];  
            for (int j = 0; j < n; j++) {  
                String s = br.readLine();  
                for (int k = 0; k < n; k++) {  
                    weights[j][k] = Integer.parseInt(s.substring(k, k + 1));  
                    distances[j][k] = Integer.MAX_VALUE;  
                }  
            }  
            Pair start = new Pair(0, new int[]{0, 0});  
            distances[0][0] = 0;  
            dijkstra(start);  
            System.out.println("#" + i + " " + distances[n - 1][n - 1]);  
        }  
    }  

    private static void dijkstra(Pair start) {  
        int[] dx = new int[]{0, 1, 0, -1};  
        int[] dy = new int[]{1, 0, -1, 0};  

        Queue<Pair> pq = new PriorityQueue();  
        pq.add(start);  

        while (!pq.isEmpty()) {  
            Pair crt = pq.poll();  
            int dist = crt.dist;  
            int[] now = crt.node;  

            if (distances[now[0]][now[1]] < dist) {  
                continue;  
            }  

            for (int i = 0; i < 4; i++) {  
                int newY = now[0] + dy[i];  
                int newX = now[1] + dx[i];  
                if (inRange(newY, newX)){  
                    if (distances[newY][newX] > dist + weights[newY][newX]) {  
                        int cost = dist + weights[newY][newX];  
                        distances[newY][newX] = cost;  
                        pq.add(new Pair(cost, new int[]{newY, newX}));  
                    }  
                }  
            }  
        }  
    }  

    private static boolean inRange(int y, int x) {  
        return y >= 0 && y < n && x >= 0 && x < n;  
    }  

    private static class Pair implements Comparable<Pair> {  
        private int dist;  
        private int[] node;  

        private Pair(int dist, int[] node) {  
            this.dist = dist;  
            this.node = node;  
        }  

        @Override  
        public int compareTo(Pair o) {  
            if (this.dist == o.dist) {  
                if (this.node[0] == o.node[0]) {  
                    return this.node[1] - o.node[1];  
                }  
                return this.node[0] - o.node[0];  
            }  
            return this.dist - o.dist;  
        }  
    }  
}