문제링크

다익스트라 알고리즘에 익숙해지기 위해서 최소비용 구하기를 풀고나서, 바로 풀이하였다.

풀이

이 문제는 출발지(A)에서 목적지(B)까지 이동하는 최소 비용뿐만 아니라, 해당 경로와 거치는 도시의 개수까지 출력해야 한다.
이를 해결하기 위해 기존의 다익스트라 알고리즘을 변형하여 최소 비용 갱신과 경로 추적을 동시에 수행하는 방식으로 접근했다.

기본적인 다익스트라 알고리즘에서는 dist 배열을 사용하여 출발점에서 각 도시에 도달하는 최소 비용을 저장한다. 하지만 이 문제에서는 최소 비용뿐만 아니라 경로도 추적해야 하므로, dist 배열을 Node 객체 배열로 변경하였다.

Node 클래스는 index와 cost 두 개의 변수를 가진다. dist 배열에서 Node 클래스 변수들의 의미는 다음과 같다.

• index : 해당 노드(도시)까지의 최소 비용을 만들기 위해 경유한 이전 도시의 번호를 저장
• cost : 해당 노드까지의 최소 비용을 저장

이제 다익스트라 알고리즘을 수행하면서, 거리 갱신과 동시에 경유한 도시를 기록한다.

최소 비용이 계산된 후, 목적지에 저장된 Node 객체의 index 값을 활용하여 경로를 추적한다. 문제의 예시 입력에 대한 최종 dist 배열은 아래와 같은 형태가 된다.

도시 번호	경유한 도시 번호(index)	최소비용(cost)
1	1	0
2	1	2
3	1	3
4	1	1
5	4	4

목적지부터 시작해 이전 도시를 따라가면서 route 배열에 저장하고, 경유한 도시 개수도 함께 계산한다.
이렇게 저장된 경로를 뒤집으면 출발지부터 목적지까지의 이동 경로가 완성된다.

코드

package BOJ;

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

public class sol11779 {
    static int n, m;
    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[start].add(new Node(end, cost));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int startTarget = Integer.parseInt(st.nextToken());
        int endTarget = Integer.parseInt(st.nextToken());

        Node[] result = dijkstra(n, startTarget);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int minCost = result[endTarget].cost;
        bw.write(minCost + "\n");

        int[] route = new int[100001];  //  경로를 저장하기 위한 배열
        int count = 0;
        route[count++] = endTarget; //  목적지의 도시 번호를 저장
        while (endTarget != startTarget) {  //  목적지 도시부터 경로를 추적
            endTarget = result[endTarget].index;
            route[count++] = endTarget;
        }
        bw.write(count + "\n");
        
        for (int i = count - 1; i >= 0; i--) {
            bw.write(route[i] + " ");
        }

        bw.flush();
        bw.close();
    }

    public static Node[] dijkstra(int n, int start) {
        boolean[] visited = new boolean[n + 1];
        Node[] dist = new Node[n + 1];
        int INF = Integer.MAX_VALUE;
        for (int i = 0; i < n + 1; i++) {
            dist[i] = new Node(i, INF);
        }
        dist[start] = new Node(start, 0);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int curr = pq.poll().index;
            if (visited[curr]) {
                continue;
            }
            visited[curr] = true;
            for (Node next : graph[curr]) {
                if (dist[next.index].cost > dist[curr].cost + next.cost) {
                    dist[next.index].cost = dist[curr].cost + next.cost;
                    dist[next.index].index = curr;  //  경유한 도시의 번호로 업데이트
                    pq.offer(new Node(next.index, dist[next.index].cost));
                }
            }
        }
        return dist;
    }

    public static class Node implements Comparable<Node> {
        int index, cost;

        public Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }

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