[Python] 백준 - 11780 플로이드 2

문제

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

출력

먼저, n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

그 다음에는 n×n개의 줄을 출력해야 한다. i×n+j번째 줄에는 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력한다. 그 다음, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력한다. 이때, 도시 i와 도시 j도 출력해야 한다. 만약, i에서 j로 갈 수 없는 경우에는 0을 출력한다.

 

문제해결방법 - (구글링 참조)

 

1. 어렵다. 3가지 방법이 있는데, 재귀 함수 방법 정도만 떠올릴 수 있을 것 같다.

2. 플로이드 알고리즘에 최소경로값이 저장되는 원리도 사실 완벽하게 이해는 잘 안된다.

   

최소경로가 2 5 1 3 일 때, dp[2][1] 에 중간경로가 5가 붙으니, 나중에 갱신되는 것 아닌가 헷갈렸다.

하지만 결국 이해한 것은, [2] k=5 [1] + [1][3] 이나, [2][5] + [5] k=1 [3] 이나 값은 같기 때문에 갱신에 누락은 없다는 점이 생각되었다.

 

밑의 3방법은

 

dp[x][y]의 중간경로를 포함한 값이 최소경로비용으로 갱신될 때,

 

1) trace[x][y]에 그냥 중간경로 k 를 저장해두느냐,

2) trace[x][y]에 끝점 y의 직전 경로 trace[k][y] 를 저장해두느냐,

3) trace[x][y]에 중간경로 자체를 저장해두느냐의 차이가 있다. 

 

어렵지만, 코드 자체는 이해하기 어렵지 않은 것 같다.

(이 것을 실전 시 떠올릴 수 있을지는 미지수이다;)

 

 

 

 

 

 

- 중간경로를 찾아주는 재귀 함수를 이용한 방법

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = sys.maxsize
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
trace = [[0 for _ in range(n+1)] for _ in range(n+1)]

# dp[시작점][끝점]의 처음 주어지는 비용 반영
for _ in range(m):
	s, e, cost = map(int, input().split())
	dp[s][e] = min(dp[s][e], cost)


# (x, y) 사이의 경로를 찾아주는 함수
def tracer(x, y):
	if trace[x][y] == 0:
		return []
	k = trace[x][y]
	t1 = tracer(x, k)
	t2 = tracer(k, y)
	return t1 + [k] + t2

# 플로이드와샬 알고리즘 - dp에 중간경로를 포함하여 최소경로값을 저장하고, trace에 중간경로를 저장 (*직전경로가 아님)
for k in range(1, n+1):
	for x in range(1, n+1):
		dp[x][x] = 0
		for y in range(1, n+1):
			if dp[x][y] > dp[x][k]+dp[k][y]:
				dp[x][y] = dp[x][k]+dp[k][y]
				trace[x][y] = k

#dp를 출력 
for x in range(1, n+1):
	for y in range(1, n+1):
		if dp[x][y] == INF:
			print(0, end=' ')
		else:
			print(dp[x][y], end=' ')
	print()

# 중간경로의 갯수와 경로를 출력, dp[x][x]이면 0 출력
for x in range(1, n+1):
	for y in range(1, n+1):
		if dp[x][y] == INF or dp[x][y] == 0:
			print(0)
		else:
			res = [x] + tracer(x, y) + [y]
			print(len(res), *res)

 

- trace리스트에 직전경로를 저장하여, 역추적하는 방법

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = sys.maxsize
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
trace = [[0 for _ in range(n+1)] for _ in range(n+1)]

# dp[시작점][끝점] 에 첫 비용을 저장하고, trace[시작점][끝점]에 시작점을 저장한다.
for _ in range(m):
	s, e, cost = map(int, input().split())
	dp[s][e] = min(dp[s][e], cost)
	trace[s][e] = s

# 플로이드 와샬 알고리즘으로 dp값을 최소경로 비용으로 갱신한다.
# trace리스트에 "직전경로"를 저장한다. (중간경로가 아님.)
for k in range(1, n+1):
	dp[k][k] = 0
	for x in range(1, n+1):
		for y in range(1, n+1):
			if dp[x][y] > dp[x][k]+dp[k][y]:
				dp[x][y] = dp[x][k]+dp[k][y]
				trace[x][y] = trace[k][y]

# dp 출력
for x in range(1, n+1):
	for y in range(1, n+1):
		if dp[x][y] == INF:
			print(0, end=' ')
		else:
			print(dp[x][y], end=' ')
	print()

# 역추적하여 직전경로를 t에 담고, 경로의 갯수와 t를 거꾸로 출력한다.
for x in range(1, n+1):
	for y in range(1, n+1):
		if dp[x][y] == INF or dp[x][y] == 0:
			print(0)
		else:
			t = [y]
			idx = y
			while True:
				if idx == x:
					break
				t.append(trace[x][idx])
				idx = trace[x][idx]
			print(len(t), *t[::-1])

 

 

-  trace리스트에 시작점, 중간경로를 저장해놓고, 끝점만 역추적할 때, 붙이는 방법(이거 어떻게 떠올리냐;;;)

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = sys.maxsize
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
t = [[0 for _ in range(n+1)] for _ in range(n+1)]

# dp[시작점][끝점]에 첫 비용을 저장하고, t[시작점][끝점]에 [시작점](경로저장리스트)을 저장한다.
for _ in range(m):
	start, end, cost = map(int, input().split())
	dp[start][end] = min(dp[start][end], cost)
	t[start][end] = [start]

# 플로이드 와샬 알고리즘으로 dp에 최소경로비용을 저장하고, t에 경로들을 저장한다.
''' t[2][3]의 경로가 2 4 5 1 3 일때, 
k = 1 에, 5 1, 1 3부터 [5, 1]이 경로로 저장되고, 
k = 4일 때, 2 4, 4 5 에 [2, 4]가 저장되고, 
t[2][3]일 때, 
k = 5로 반영된 값이 최소경로값이기에 t[2][5] ([2, 4]) + t[5][3] ([5, 1]) = [2, 4, 5, 1]이 된다. 
마지막 경로는 역추적할 때, 붙여준다.
'''
for k in range(1, n+1):
	dp[k][k] = 0
	for i in range(1, n+1):
		for j in range(1, n+1):
			if dp[i][j] > dp[i][k]+dp[k][j]:
				dp[i][j] = dp[i][k]+dp[k][j]
				t[i][j] = t[i][k]+t[k][j]

# dp 출력
for i in range(1, n+1):
	for j in range(1, n+1):
		if dp[i][j] == INF:
			print(0, end=' ')
		else:
			print(dp[i][j], end=' ')
	print()

# t 출력 (마지막 경로는 붙여줘야 한다.)
for i in range(1, n+1):
	for j in range(1, n+1):
		if dp[i][j] == INF or dp[i][j] == 0:
			print(0)
		else:
			print(len(t[i][j])+1, *t[i][j], j)