[Python Algorithm] 백준 플로이드 - 11404

풀이 과정

모든 도시 쌍에 대하여 필요한 최소 비용을 구하는 문제이므로 플로이드-워셜 알고리즘을 사용하면 된다.

어차피 모든 경우에 대해 필요한 최소 비용을 구해야하기 때문에 graph를 따로 두지 않고, 처음부터 distance 배열에 거리를 저장하는 방식으로 구현하였다.

최종 코드

INF = float('INF')
N = int(input())
M = int(input())

distance = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for _ in range(M):
	start, end, weight = map(int, input().split(' '))
	if distance[start][end] > weight:
		distance[start][end] = weight	
	
for k in range(1, N+1): #거치는 점
	for i in range(1, N+1): #시작
		for j in range(1, N+1): #끝
			if i != j and distance[i][j] > distance[i][k] + distance[k][j]:
				distance[i][j] = distance[i][k] + distance[k][j]

for i in range(1, len(distance)):
	for j in range(1, len(distance[i])):
		print(0, end=' ') if distance[i][j] == INF else print(distance[i][j], end=' ')
	print()

결과

Link

플로이드 문제 출처
GitHub 코드