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

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

11779번: 최소비용 구하기 2

---

풀이 과정

어떤 도시에서 출발해, 도착지점까지 버스를 타고 가는 최소 비용을 구하고, 그 경로를 출력하는 문제이다.

 

음수 가중치가 존재하지 않는, 가중치가 존재하는 그래프에서의 최소 비용을 구하는 문제이므로 다익스트라 알고리즘을 활용해서 문제를 해결할 수 있다. 우선순위 큐를 활용한 다익스트라 알고리즘의 시간복잡도는 O(ElogV)이므로 TLE도 발생하지 않음을 확인할 수 있다.

 

다익스트라 알고리즘 진행 도중, 다음 정점까지 가는 비용이 현재 정점을 경유하는 경우가 더 저렴하면, pre[nxt] = cur로 nxt 정점을 최소 비용으로 방문하기 위해서는 이전 정점으로 cur 정점을 거쳐야 한다는 점을 표시해주자. 그렇다면 end까지 도착했을때, end부터 계속 pre 배열을 확인하면 start부터 end까지 최소비용으로 방문했을 때의 경로를 역순으로 얻어낼 수 있으며, 이를 다시 뒤집어서 출력하면 경로를 반환할 수 있다.

---

소스 코드

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 {
		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<>(); // u번째 버스에서 출발하는 (비용, 도착지) 버스 노선을 저장한다
		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; // 시작지로부터의 비용을 MAX로 초기화한다
		}
		
		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}); // u번째 버스에서 출발하는 버스들의 리스트에 (비용, 도착지) 삽입
		}
		
		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; // 시작지점까지의 거리는 0
		pq.add(new int[] {d[start], start}); // pq에 가장 거리가 가까운 점을 넣는다
		
		// 다익스트라 진행
		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까지의 경로중 가장 비용이 적으므로, 저장한다
				pre[nxt[1]] = cur[1];
			}
		}
		
		// 최소 비용을 출력한다
		sb.append(d[end]).append('\n');
		
		// 도착정점부터 pre 배열을 살펴보며 최소 비용으로 순회하는 경로를 역순으로 스택에 삽입한다
		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());
	}
}