Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

27. 동적 계획법과 최단거리 역추적

지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.

Java / Python

9. 플로이드 2

11780번

플로이드 알고리즘에서 최단경로를 출력하는 문제

이번 문제는 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하는 문제입니다.
플로이드와샬 알고리즘을 활용해 최단경로비용 + 최단경로를 구하는 문제입니다.

• Java

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

public class Main {
	static int[][] map;
	static int[][] dist;
	static int N, M;
	static int INF = 10000001;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		Stack<Integer> stack = new Stack<>();
		dist = new int[N + 1][N + 1];
		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dist[i][j] = INF;
				if (i != j)
					map[i][j] = INF;
			}
		}

		for (int i = 0; i < M; i++) {
			String[] input = br.readLine().split(" ");
			int start = Integer.parseInt(input[0]);
			int end = Integer.parseInt(input[1]);
			int cost = Integer.parseInt(input[2]);

			map[start][end] = Math.min(map[start][end], cost);
			dist[start][end] = start;
		}
		floydWarshall();

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j] == INF)
					sb.append(0 + " ");
				else
					sb.append(map[i][j] + " ");
			}
			sb.append("\n");
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist[i][j] == INF)
					sb.append(0 + "\n");

				else {
					int pre = j;
					stack.push(j);
					while (i != dist[i][pre]) {
						pre = dist[i][pre];
						stack.push(pre);
					}
					sb.append((stack.size() + 1) + " ");
					sb.append(i + " ");
					while (!stack.empty())
						sb.append(stack.pop() + " ");
					sb.append("\n");
				}
			}
		}
		bw.write(sb.toString());

		bw.flush();
		br.close();
		bw.close();
	}

	public static void floydWarshall() {
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
						dist[i][j] = dist[k][j];
					}
				}
			}
		}
	}
}

• Python

import sys, math
input = sys.stdin.readline
N = int(input())
M = int(input())
visit = [[0] * (N+1) for _ in range(N+1)]
dist = [[math.inf] * (N+1) for _ in range(N+1)]

for _ in range(M):
	a, b, c = map(int,input().split())
	dist[a][b] = min(dist[a][b], c)

def find_path(i, j, visit, result):
	if visit[i][j] == 0:
		result.append(i)
		if i != j:
			result.append(j)
	else:
		k = visit[i][j]
		find_path(i, k, visit, result)
		result.pop()
		find_path(k, j, visit, result)

for k in range(1, N+1):
	for i in range(1, N+1):
		for j in range(1, N+1):
			if i != j:
				if dist[i][j] > dist[i][k] + dist[k][j]:
					visit[i][j] = k
					dist[i][j] = dist[i][k] + dist[k][j]

for i in dist[1:]:
	for j in i[1:]:
		print(0 if j == math.inf else j, end = ' ')
	print()

for i in range(1, N+1):
	for j in range(1, N+1):
		if dist[i][j] == math.inf or i == j:
			print(0)
		else:
			result = []
			find_path(i, j, visit, result)
			print(len(result), *result)