[백준] 11779번 최소비용 구하기2

문제 설명

• https://www.acmicpc.net/problem/11779
• Gold 3
• 풀이시간 : 25분

문제 풀이

• 기본적인 다익스트라 알고리즘에 경로 역추적 문제이다.
• 다익스트라 알고리즘을 사용하되 특정 노드에 이전 노드를 저장하는 배열을 두고 최종적으로 해당 배열을 탐색하며 경로 및 도시 수를 출력하면 된다.

소스 코드 (JAVA)

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

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point implements Comparable<Point>{
        int n, d;

        public Point(int n, int d) {
            this.n = n;
            this.d = d;
        }

        @Override
        public int compareTo(Point o) {
            return this.d - o.d;
        }
    }

    static int N, M, S, D;
    static int[] dist, pre;
    static List<List<Point>> map = new ArrayList<>();


    static void solve() throws IOException {
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(S, 0));
        dist[S] = 0;
        pre[S] = 0;

        while(!pq.isEmpty()) {
            Point cur = pq.poll();
            if (cur.d > dist[cur.n]) continue;

            for (int i = 0; i < map.get(cur.n).size(); i++) {
                int nNode = map.get(cur.n).get(i).n;
                int nDist = cur.d + map.get(cur.n).get(i).d;
                if (nDist < dist[nNode]) {
                    dist[nNode] = nDist;
                    pre[nNode] = cur.n;
                    pq.add(new Point(nNode, nDist));
                }
            }
        }

        //결과 출력
        int cnt = 0;
        int cur = D;
        Stack<Integer> st = new Stack<>();
        while(cur != 0) {
            st.add(cur);
            cnt++;
            cur = pre[cur];
        }
        bw.write(dist[D] + "\n");
        bw.write(cnt + "\n");
        while(!st.isEmpty()) {
            Integer n = st.pop();
            bw.write(n + " ");
        }
        bw.flush();

    }

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

        //초기화
        dist = new int[N+1];
        pre = new int[N+1];
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            map.get(from).add(new Point(to, d));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * 최소비용 구하기2 (13:48)
 *
 * N : 도시 개수 (<=1000)
 * M : 방향 간선 (<=10만)
 *
 * N
 * M
 * a b c
 * ...
 *
 *
 * A -> B로 가는 최소비용과 경로 출력
 * - 다익스트라로 최소비용 구하기
 * - 각 노드 이전 노드를 저장하는 배열을 통해 경로 출력
 *
 */