11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
INF = float("inf")
graph = [[INF]*(n+1) for _ in range(n+1)]
for _ in range(m):
start, end, cost = map(int,input().split())
graph[start][end] = min(graph[start][end],cost)
for i in range(1,n+1):
graph[i][i] = 0
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
for i in range(1,n+1):
for j in range(1,n+1):
if graph[i][j] == INF:
print(0, end=" ")
else:
print(graph[i][j],end=" ")
print()이번 문제는 플로이드 워셜 알고리즘을 사용하여 '모든 지점에서 다른 모든 지점까지의 최단거리를 구하는 문제'이다.
먼저 그래프를 INF 값으로 초기화하고 대각선(i,i)의 값, 즉 자기 자신으로 가는 비용을 0으로 초기화 하였다. 그 후 3중 반복문을 사용하여 모든 경로를 graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])로 갱신시켜줌으로써 풀이할 수 있었다.
다만 다음과 같이 조심해야할 점이 2가지 있다.
- input 대신에 sys.stdin.readline을 사용해야 시간초과가 발생하지 않는다.
- "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라는 조건이 있기 때문에, 2차원 리스트로 선언된 그래프(graph)에 경로를 저장할 때 항상 최솟값(min)으로 저장해야 한다.