백준 11779 - 최소비용 구하기 2 [자바]

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

11779번: 최소비용 구하기 2

---

풀이 과정

도시와 도시 사이를 운행하는 버스가 있을 때, A번째 도시에서 B번째 도시로 가는 최소비용과 경로를 출력하는 문제이다.

• 음수 간선 없는 최단거리 -> 다익스트라 알고리즘
• 특정 정점 i를 최단거리로 방문하기 위해서 바로 직전 정점으로 j를 방문해야 한다면 pre[i] = j로 표시
• 마지막 정점에서 역추적하면서 최단경로를 역순으로 뽑아낼 수 있으며, 이를 다시 역순으로 출력해주면 된다.

---

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException { // 메모리 56776KB 시간 632ms
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<int[]>> al = new ArrayList<>();
		int[] d = new int[n+1];
		int[] pre = new int[n+1];
		
		for (int i = 0; i <= n; i++) {
			al.add(new ArrayList<>());
			d[i] = Integer.MAX_VALUE;
		}
		
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			al.get(u).add(new int[] {w, v});
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
		d[start] = 0;
		pq.add(new int[] {d[start], start});
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			
			if (cur[0] != d[cur[1]]) continue;
			
			for (int[] nxt : al.get(cur[1])) {
				if (d[nxt[1]] <= d[cur[1]] + nxt[0]) continue;
				d[nxt[1]] = d[cur[1]] + nxt[0];
				pq.add(new int[] {d[nxt[1]], nxt[1]});
				
				// nxt를 갈 때 cur를 거쳐가는게 더 빠르다면, pre[nxt] = cur로 설정
				pre[nxt[1]] = cur[1]; 
			}
		}
		
		sb.append(d[end]).append('\n');
		
		
		// 스택을 이용하여 끝에서부터 역추적
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int index = end;
		q.addLast(index);
		
		while (index != start) {
			index = pre[index];
			q.addLast(index);
		}
		
		sb.append(q.size()).append('\n');
		
		// 스택에 넣은 뒤 다시 다 빼면 뒤집어서 나온다
		while(!q.isEmpty()) {
			sb.append(q.pollLast()).append(' ');
		}
		
		System.out.print(sb.toString());
	}
}