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

🔗 문제 링크

BOJ 11779번: 최소비용 구하기 2

11779번: 최소비용 구하기 2

 

📝 풀이 과정

다익스트라로 + 경로를 구하는 문제이다.

 

다익스트라는 dist 배열을 통해 현재 노드에서부터 다음 노드로 이동하는 비용이 최소 비용이 될 때 갱신하는 방법을 사용하는데, 이 때 거리를 갱신하면서 현재 노드의 위치를 함께 저장하면 경로를 구할 수 있다.

 

 

만약, 1번에서 3번으로 이동했다면 3번 전에 1번 노드를 방문했다는 의미가 되고, prev[3] = 1가 되는 것이다. 최종적으로 도착노드에서부터 역방향으로 시작노드까지 구할 수 있게 된다.

 

 

Deque<Integer> stack = new ArrayDeque<>();
int city = dest;

while (city != 0) {
  stack.push(city);
  city = prev[city];
}

따라서, 역방향으로 구한 경로를 뒤집기 위해 Stack을 사용해 뒤집어주고 출력하면 원래의 경로가 나오게 된다.

 

 

💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        ArrayList<int[]>[] adj = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++)
            adj[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) 
            adj[sc.nextInt()].add(new int[]{sc.nextInt(), sc.nextInt()});

        int start = sc.nextInt(), dest = sc.nextInt();

        int[] dist = new int[N + 1];
        int[] prev = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        queue.add(new int[]{start, 0});
        dist[start] = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            if (dist[cur[0]] < cur[1]) continue;
            if (dest == cur[0]) break;

            for (int[] a : adj[cur[0]]) {
                if (dist[a[0]] <= cur[1] + a[1]) continue;

                queue.add(new int[]{a[0], cur[1] + a[1]});
                prev[a[0]] = cur[0];
                dist[a[0]] = cur[1] + a[1];
            }
        }

        Deque<Integer> stack = new ArrayDeque<>();
        int city = dest;

        while (city != 0) {
            stack.push(city);
            city = prev[city];
        }

        System.out.println(dist[dest]);
        System.out.println(stack.size());
        while (!stack.isEmpty())
            System.out.print(stack.pop() + " ");
        System.out.println();

    }
}

 

📊 제출 결과