난이도 : 골드 4
유형 : 최단거리
https://www.acmicpc.net/problem/11404
문제 접근
도시의 개수 N (1 ≤ N ≤ 100)
버스의 개수 M (1 ≤ M ≤ 100,000)
모든 도시 쌍 (i, j)에 대해 최소 비용을 구하는 문제이다.
여기에는 플로이드-워셜 알고리즘을 적용해야 한다.
그 이유는 다음과 같다.
| 구분 | 내용 |
|---|---|
| 시작점이 하나 | 다익스트라 / 벨만-포드 |
| 모든 정점 → 모든 정점 | ✅ 플로이드 워셜(Floyd-Warshall) |
| 음수 가중치 | ❌ 없음 (양수만 있음) → 플로이드 OK |
모든 정점에서 모든 정점으로의 최소 비용을 구해야한다면 플로이드-워셜
플로이드 워셜 (Floyd-Warshall) 알고리즘
플로이드 워셜 알고리즘은 모든 정점 쌍 (i, j)에 대해 최단 경로를 구하는 알고리즘이다.
3중 for문으로 모든 정점 쌍에 대한 최단거리를 구하기에 시간 복잡도가 O(N^3) 이다.
구현아이디어는 다음과 같다.
- 거리 배열 초기화
distance[i][j]: i번 도시 -> j번 도시 로 가는. 최소 비용- 처음에
-distance[i][i] = 0(자기 자신까지의 비용은 0)- 간선이 존재하면 해당 비용으로 최화
- 나머지는 INF ( 도달 할 수 없음을 의미 )
- 입력 간선 처리
distance[i][j] = min(distance[i][j], c, 중복된 간선 중. 가장 저렴한 것만 저장하기 위함
즉 앞서 저장한 distance[i][j]이 이제 받는 c 값보다 더 작다면 그걸로 저장한다는 뜻이다.
- 거리 갱신
모든 경유지 k에 대해 다음을 반복한다.
for k in range(1, N+1): # 경유지
for i in range(1, N+1): # 출발 도시
for j in range(1, N+1): # 도착 도시
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
# i->j 직접 비용 보다 i->k->j 로 우회해서 가는 비용이 더 작다면, 그 값으로 갱신플로이드 워셜 알고리즘은 3중포문을 돌리기 때문에 시간복잡도가 O(N^3)이다.
N이 100 이하 일때만 실용적이라 할 수 있다.
해답 및 풀이
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input()) # n의 범위가 100 이하이기에? 플로이드 워셜알고리즘인 3중포문을 돌려도 괜찮다.
m = int(input())
# 1. 거리 배열 초기화
distance = [ [INF] * (n+1) for _ in range(n+1) ]
for i in range(1, n+1):
distance[i][i] = 0 # 자기 자신은 0
# 2. 입력 간선 처리
for _ in range(m):
a, b, c = map(int,input().split())
distance[a][b] = min(distance[a][b], c) #중복된 간선 중. 가장 저렴한 것만 저장
# 3. 플로이드 워셜 수행
for k in range(1, n+1): # 경유지
for i in range(1, n+1): # 출발지
for j in range(1, n+1): # 도착지
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
# i -> j 보다 i -> k -> j 로 우회하여 가는게 더 작다면, 그걸로 갱신
# 출력
for i in range(1, n+1):
for j in range(1, n+1):
if distance[i][j] == INF:
print(0, end=' ') # end=' '는 출력값을 한 줄로 이어붙이기 위해 사용
else:
print(distance[i][j], end= ' ')
print() # 한 줄 출력이 끝났으니 줄바꿈
distance라는 2차원행렬에 [i][j] 라면 i->j 로가는 최소비용을 min() 을 이용하여 저장하는 알고리즘이었다.
플로이드-워셜 알고리즘이라고 해서 뭔가 있어보이지만 그냥 3중 포문 돌리는 알고리즘이다.
간단하고, 강력하다 노드 개수가 100정도 이하라면 쓸만하다고 한다.
마지막 출력문에 잡기술도 배웠다.
print(프린트하고 싶은 것 , end=' ')
end=' ' 로 줄바꿈 하지않고 공백으로 이어가는 것 외워두어야 할 것 같고
줄바꿈은 print() 으로 할 수 있다는 사실도 알게 되었다.
