[Python] BOJ 11780 - 플로이드 2

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

11780번: 플로이드 2

# '플로이드' 문제를 응용한 플로이드 2 문제이다.

# a도시에서 b도시까지 가는 비용뿐만 아니라, a도시에서 b도시까지 가는 경로를 모두 출력해줘야 한다.

# 경로를 찾는 코드를 구현하는데 꽤 많은 시간이 걸렸다...

 

# 우선 path배열을 따로 선언해주고 a도시에서 b도시로 가는 a,b,c를 입력받을 때

   dist[a][b]뿐만 아니라 path[a][b]도 [a, b]로 갱신해주었다. (a -> b라는 뜻)

 

# 플로이드-와샬 알고리즘을 통해 dist[i][j]를 갱신할 때마다

   path[i][j]도 path[i][k][  :-1] + path[k][j]로 갱신해주었다.

 

# 플로이드 문제처럼 각각 a도시에서 b도시로 가는 비용을 출력해주고

   n x n줄에 걸쳐 path[i][j]의 길이와 path[i][j]의 원소들을 출력해준다.

   (dist[i][j]가 math.inf이거나 i == j이면, 갈 수 없으므로 0 출력)

 

# 예제에서 2번 도시에서 1번 도시로 가는경우 2 -> 4 -> 5 -> 1 경로로 갈 수 있는데,

   처음에 dist[2][5] > dist[2][4] + dist[4][5] 이므로 dist[2][5] = 5가 되고

   path[2][5] = path[2][4][  :-1] + path[4][5] = [2] + [4, 5] = [2, 4, 5]가 된다.

   그 뒤에 dist[2][1] > dist[2][5] + dist[5][1] 이므로 dist[2][1] = 12가 되고

   path[2][1] = path[2][5][  :-1] + path[5][1] = [2, 4] + [5, 1] = [2, 4, 5, 1]이 된다.

 

*** 2번 도시에서 1번 도시로 가는 경우(dist[2][1])는 k가 1부터 5까지 증가하므로

     원래 dist[2][4] + dist[4][1]에서 갱신이 되어야 한다.

     그러나 dist[4][1]의 값이 dist[2][1]을 구할 때 inf값이므로

     갱신이 되지 않아서 k가 5일때 dist[2][5] + dist[5][1]을 구할 때 갱신이 된다.

 

import sys, math
input = sys.stdin.readline
n = int(input())
m = int(input())
path = [[[] for _ in range(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)
	path[a][b] = [a, b]

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]:
					dist[i][j] = dist[i][k] + dist[k][j]
					path[i][j] = path[i][k][:-1] + path[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:
			print(len(path[i][j]), *path[i][j])

 

# 다른 맞은 사람들의 코드를 보니 경로추적을 '백트래킹'기법과 비슷하게 할 수도 있다는 것을 배웠다!

# 위 코드랑 작동원리는 비슷하다. 

  2번 도시에서 1번 도시로 가는경우: 2 -> 4 -> 5 -> 1 이고 visited[2][5] = 4, visited[2][1] = 5이다.

  find_path(2, 1, visited, ans)에서 visited[2][1]이 5이므로

  1. find_path(2, 5, visited, ans)

  2. ans.pop()

  3. find_path(5, 1, visited, ans)을 실행한다.

 

  1. find_path(2, 5, visited, ans)에서 visited[2][5] = 4이므로 또

     1-1. find_path(2, 4, visited, ans)

     1-2. ans.pop()

     1-3. find_path(4, 5, visited, ans)을 실행한다.

 

     1-1: find_path(2, 4, visited, ans)에서 visited[2][4]는 0이므로 ans = [2]를 넣어주고 

           i != j 이므로 ans = [2, 4]가 된다.

     1-2: ans.pop()을 해서 4를 pop한 뒤,

     1-3: find_path(4, 5, visited, ans)에서 visited[4][5] = 0, i != j 이므로 ans = [2, 4, 5]가 된다.

 

  2. ans.pop()을 해서 5를 pop 한 뒤

  3. find_path(5, 1, visited, ans)에서 visited[5][1] = 0, i != j 이므로 ans = [2, 4, 5, 1]이 된다.

 

import sys, math
input = sys.stdin.readline
n = int(input())
m = int(input())
visited = [[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, visited, ans):
	if visited[i][j] == 0:
		ans.append(i)
		if i != j:
			ans.append(j)
	else:
		k = visited[i][j]
		find_path(i, k, visited, ans)
		ans.pop()
		find_path(k, j, visited, ans)

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]:
					visited[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:
			ans = []
			find_path(i, j, visited, ans)
			print(len(ans), *ans)

(solved.ac 티어: 골드 3)

 

# 재귀를 사용한 아래코드가 100ms정도 빠르다.