백준 11779번 최소비용 구하기 2 (JAVA)

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

11779번: 최소비용 구하기 2

 

최단거리 문제이다.

음의 사이클이 발생할 여지가 없기때문에 다익스트라 알고리즘으로 풀이하면 된다.

최단거리에 사용된 경로를 저장해야하는 점이 변형된 포인트라고 할 수 있다.

경로를 역추적하는데에는 두가지 방식이 있는데, 하나는 dp[prev] + 경로.cost == dp[now] 인 경우를 찾아가면서 역으로 추적하는 것이고, 이번 경우에는 애초에 최단거리를 갱신할 때 prev 배열에 이전 노드의 위치를 넣었고, prev[끝 노드] 부터 역으로 돌아가면서 경로를 찾는 방법을 선택했다.

 

public class BOJ_11779_최소비용구하기2 {
	static Function<String, Integer> stoi = Integer::parseInt;
	static int N, M, start, end;
	static ArrayList<int[]> routes[];
	static int[] dp, prev;
	static final int INF = (int) 1e9;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = stoi.apply(br.readLine());
		M = stoi.apply(br.readLine());
		routes = new ArrayList[N + 1];
		dp = new int[N + 1];
		prev = new int[N + 1];
		Arrays.fill(dp, INF);
		for (int i = 1; i <= N; i++) {
			routes[i] = new ArrayList<int[]>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			routes[stoi.apply(st.nextToken())]
					.add(new int[] { stoi.apply(st.nextToken()), stoi.apply(st.nextToken()) });
		}
		st = new StringTokenizer(br.readLine());
		start = stoi.apply(st.nextToken());
		end = stoi.apply(st.nextToken());
		dijk();
		trace();
	}

	private static void trace() {
		Deque<Integer> stack = new ArrayDeque<>();
		stack.add(end);
		while (true) {
			if (end == start) {
				break;
			}
			stack.add(prev[end]);
			end = prev[end];
		}
		System.out.println(stack.size());
		while (!stack.isEmpty()) {
			System.out.print(stack.pollLast() + " ");
		}
	}

	private static void dijk() {
		PriorityQueue<int[]> pQ = new PriorityQueue<>(Comparator.comparingInt(i -> i[1]));
		pQ.add(new int[] { start, 0 });
		dp[start] = 0;

		while (!pQ.isEmpty()) {
			int[] cur = pQ.poll();
			if (dp[cur[0]] < cur[1]) {
				continue;
			}
			if (cur[0] == end) {
				break;
			}
			for (int[] e : routes[cur[0]]) {
				if (dp[e[0]] > e[1] + dp[cur[0]]) {
					dp[e[0]] = e[1] + cur[1];
					pQ.add(new int[] { e[0], dp[e[0]] });
					prev[e[0]] = cur[0];
				}
			}
		}
		System.out.println(dp[end]);
	}

}