[백준/Java] 1719 택배

문제 링크

https://www.acmicpc.net/problem/1719

접근 방법

다익스트라 알고리즘은 "어떤 노드까지의 최단거리를 알 때, 그 노드와 연결된 노드들의 최단 거리를 갱신"하며 정답을 구하는 알고리즘이다.

그러한 알고리즘의 특징을 이용해서 다음과 같은 접근을 하였다.

다익스트라 알고리즘을 진행할 때, 알고리즘의 효율성을 위해 우선순위 큐를 사용한다. 우선순위 큐에는 최단 거리가 갱신된 노드가 담긴다.

우선순위 큐에서 어떤 노드 A가 나온다고 가정해보자. (우선순위 큐의 top이 노드 A)

• 노드 A로 향하는 최단 거리는 확정되었다. (큐의 내용과 실제 노드 A의 최단 거리를 비교해야함)
• A 노드가 다익스트라 알고리즘을 실행한 루트 노드가 아니라면 루트 노드에서 A 노드로 향하는 이전 노드가 있을 것이다.
• (Root Node → i Node → i_1 Node → ... → A Node) 이런식으로 말이다.
• 노드 A로 향하는 최단 거리는 확정되었기 때문에 Root Node → A Node 의 경로표를 작성할 수 있게 된다.
• 경로표를 routeTable[i][j] 이라고 하면... routeTable[root][A]를 다음과 같이 정의 가능하다.
• routeTable[root][A] = routeTable[root][prevOfA] (prevOfA는 A 노드의 이전 노드를 의미)

 

위 접근을 그림으로 표현하면 아래와 같다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    class Node {
        int seq;
        List<Edge> connectedNodes;
        Node(int seq) {
            this.seq = seq;
            this.connectedNodes = new ArrayList<>();
        }
    }

    class Edge {
        Node dest;
        int weight;
        Edge(Node dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }

    class Triple {
        Node srcNode;
        Node destNode;
        int distance;

        Triple(Node srcNode, Node destNode, int distance) {
            this.srcNode = srcNode;
            this.destNode = destNode;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Node[] nodes = new Node[n+1];
        for (int i = 0; i <= n; i++) {
            nodes[i] = new Node(i);
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int srcSeq = Integer.parseInt(st.nextToken());
            int destSeq = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            Node srcNode = nodes[srcSeq];
            Node destNode = nodes[destSeq];
            srcNode.connectedNodes.add(new Edge(destNode, weight));
            destNode.connectedNodes.add(new Edge(srcNode, weight));
        }

        int[][] routeTable = new int[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            // 거리 배열 초기화
            int[] distanceTable = initDistanceTable(n);
            distanceTable[i] = 0;
            
            // 각 노드에 대해 dijkstra 시작
            Node startNode = nodes[i];
            
            // distance, 출발노드, 도착노드를 포함하는 객체를 우선순위큐에 삽입
            PriorityQueue<Triple> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.distance, o2.distance));
            pq.add(new Triple(startNode, startNode, 0));

            while (!pq.isEmpty()) {
                Triple t = pq.poll();
                Node callerNode = t.srcNode;
                Node destNode = t.destNode;
                int distance = t.distance;
                
                // 최단거리가 아닌 경우 무시
                if (distance > distanceTable[destNode.seq]) continue;
                
                // 경로표 갱신
                routeTable[i][destNode.seq] = getClosestNode(routeTable, i, callerNode.seq, destNode.seq);
                
                // 간선을 확인하며 최단거리 갱신
                for (Edge edge: destNode.connectedNodes) {
                    Node nextNode = edge.dest;
                    int weight = edge.weight;
                    if (distanceTable[nextNode.seq] > distance + weight) {
                        distanceTable[nextNode.seq] = distance + weight;
                        pq.add(new Triple(destNode, nextNode, distanceTable[nextNode.seq]));
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) sb.append("- ");
                else sb.append(routeTable[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private int getClosestNode(int[][] routeTable, int rootSeq, int callerSeq, int calleeSeq) {
        // 루트 노드가 이전 노드라면 현재 노드를 반환
        if (rootSeq == callerSeq) return calleeSeq;
        // 이전 노드의 경로표 값을 반환
        else return routeTable[rootSeq][callerSeq];
    }

    private int[] initDistanceTable(int n) {
        int[] distanceTable = new int[n+1];
        for (int i = 0; i <= n; i++) {
            distanceTable[i] = Integer.MAX_VALUE;
        }

        return distanceTable;
    }


}