BOJ 11779 : 최소비용 구하기 2

풀이 요약

다익스트라 + 합집합 찾기 + 약간의 백트래킹

풀이 상세

1. 최단 경로를 구하는 것은 기존의 다익스트라 알고리즘을 사용하면 쉽게 풀 수 있다.

2. 단 지금까지 지나온 부분들을 저장하기 위해, dist 값을 최신의 최단 경로로 업데이트 할 때, 지나온 구간들을 저장하는 배열 p 를 만들어 업데이트 하자.

3. 탐색을 통해 최단 경로가 찾았다면, p 배열의 각 노드 인덱스에는 최단 경로를 지나며 저장한 이전 노드 값이 있을 것이다. 아마 눈치챈 분들도 있겠지만, 유니온 파인드의 대표값 찾기를 활용하여 이를 역추적하면 된다.

배운점

• 간단하게 풀릴 거 같으면서도 따져야 할게 많은 문제였다.
• 자바 한정인지는 모르겠으나, 다익스트라에 백트래킹이 필요하다. 좋은 사례를 알게 된 건 좋은데, 생각하느라 시간이 많이 지체된건 화가 난다.

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    static int[] dist,p;
    static List<Edge> adjList[];
    static int cnt,st,ed;
    static StringBuffer ans = new StringBuffer();
    static class Edge {
        int to, dist;
        Edge(int to, int dist) {
            this.to = to;
            this.dist = dist;
        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        adjList = new ArrayList[N + 1];
        p = new int[N+1];
        dist = new int[N + 1];
        Arrays.fill(dist, (int) 1e8 + 1);
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }
        StringTokenizer stk;
        for (int i = 0; i < M; i++) {
            stk = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(stk.nextToken());
            int n2 = Integer.parseInt(stk.nextToken());
            int dist = Integer.parseInt(stk.nextToken());

            adjList[n1].add(new Edge(n2, dist));
        }

        stk = new StringTokenizer(br.readLine());
        st = Integer.parseInt(stk.nextToken());
        ed = Integer.parseInt(stk.nextToken());
    }

    private static void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> e1.dist - e2.dist);
        pq.add(new Edge(st, 0));
        dist[st] = 0;
        while (!pq.isEmpty()) {
            Edge curr = pq.poll();
            if(dist[curr.to] < curr.dist) continue;
            for (Edge next : adjList[curr.to]) {
                if (dist[next.to] > dist[curr.to] + next.dist) {
                    dist[next.to] = dist[curr.to] + next.dist;
                    p[next.to] = curr.to;
                    pq.add(new Edge(next.to, dist[next.to]));
                }
            }
        }
    }

    private static void find(int idx) {
        cnt++;
        if(st==idx) {
            ans.append(idx + " ");
            return;
        } else find(p[idx]);
        ans.append(idx + " ");
    }

    private static void output() {
        System.out.println(dist[ed]);
        System.out.println(cnt);
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        input();
        dijkstra();
        find(ed);
        output();
    }
}