[백준] 11779번. 최소비용 구하기 2(JAVA)

문제

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

---

풀이(29분)

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

public class Main {

    static int n, m; // 도시 수, 버스 수
    static ArrayList<Integer>[] channelList; // 최단 경로 저장용
    static ArrayList<Node>[] nodeList;       // 인접 노드 및 비용
    static long[] dist;                      // 최소 거리 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine()); // 도시 수
        m = Integer.parseInt(br.readLine()); // 버스 수

        // 배열 및 리스트 초기화
        channelList = new ArrayList[n + 1];
        nodeList = new ArrayList[n + 1];
        dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);

        for (int i = 0; i <= n; i++) {
            channelList[i] = new ArrayList<>();
            nodeList[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            long weight = Long.parseLong(st.nextToken());
            nodeList[start].add(new Node(end, weight));
        }

        // 출발지, 도착지 입력
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        // 다익스트라 실행
        dijkstra(start);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        sb.append(dist[end]).append("\n"); // 최소 비용
        sb.append(channelList[end].size() + 1).append("\n"); // 경로 길이

        for (int i : channelList[end]) {
            sb.append(i).append(" ");
        }
        sb.append(end); // 마지막 도착 노드
        System.out.println(sb);
    }

    // 다익스트라 알고리즘
    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n + 1];
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            int cur = curNode.end;

            if (visited[cur]) continue;
            visited[cur] = true;

            for (Node node : nodeList[cur]) {
                if (dist[node.end] > dist[cur] + node.weight) {
                    // 최단 거리 갱신 및 경로 저장
                    channelList[node.end].clear();
                    channelList[node.end].addAll(channelList[cur]);
                    channelList[node.end].add(cur);
                    dist[node.end] = dist[cur] + node.weight;
                    pq.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }

    // 노드 클래스 (우선순위 큐용)
    static class Node implements Comparable<Node> {
        int end;
        long weight;

        public Node(int end, long weight) {
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.weight, o.weight); // 오름차순 정렬
        }
    }
}

---

문제 풀이 전략

 

다익스트라 알고리즘을 활용한 최단거리 구하기 문제이다.

[도구정리] 다익스트라 알고리즘

다만, 기존 최단거리만 구하는 다익스트라 알고리즘에 경로를 저장하는 로직을 추가해야 한다.

 

추가 방식은 다음과 같다.

1. 다익스트라 알고리즘을 동일하게 수행한다.

2. 경로가 갱신되는 일이 발생한다면,

2-1. 도착 노드의 경로를 모두 초기화한다.

2-2. 도착 노드로 오게 되는 출발 노드까지의 경로를 우선 추가한다.

2-3. 마지막에 출발 노드를 추가한다.

 

위의 과정을 통해 경로를 저장한 뒤 최종적으로 자기 자신까지 포함하여 정답을 출력하면 된다.

ArrayList<>[] 자료구조는 유용하니 꼭 알아두도록 하자!