아주 간단하고, 느리지만 아주 강력한, 정점 간 최단 거리 구하는 알고리즘인 '플로이드 워셜'
이해를 정확하게 못해도 알고리즘 자체가 쉬워 무작정 외우는 경우도 많다.
하지만 이해를 정확하게 못하면 플로이드 워셜 심화 문제는 절대 손도 못댈 것이다.
이번 풀이는 플로이드 워셜 심화 문제 중 제일 먼저 맞닥뜨릴 가능성이 높은 문제인 '도망자 원숭이'라는 문제를 다뤄보겠다.
BOJ 1602 - 도망자 원숭이 링크
(2022.09.27 기준 P4)
(치팅하면 문제 속 멍멍이가 괴롭히러 감)
문제
N개의 도시와 도시들을 잇는 M개의 도로가 있고, 각 도시마다 멍멍이가 원숭이를 괴롭힐 수 있는 시간이 정해져 있고, 한 도시에서만 원숭이를 괴롭힌다.
Q개의 출발도시 S와 도착도시 T가 주어진다면, 각 Q개의 질문 별로 S에서 T로의 걸리는 최소시간
알고리즘
정점의 개수가 500개 이하이고, 간선마다 가중치가 있으며, 출발도시와 도착도시가 Q개의 질문마다 달라지므로 모든 정점 간 최단거리를 구해놓아야 한다. 그러므로, 플로이드 워셜.
풀이
기본적인 플로이드 워셜 문제만 풀었던 사람이면 이런 유형의 플로이드 워셜 문제는 처음 볼 것이다.
각 루트마다 지나온 도시의 가중치의 최대값을 최단거리에 더해야 하는데, 여기서 생각을 두 개가 들 것이다.
- 최단거리 계산 후 도시의 가중치의 최대값을 더하기
이렇게 하면 도시의 가중치가 무시되어 최단거리가 계산이 되기 때문에 안된다. 극단적으로 이렇게 생각해보자.
도시들의 가중치는 아주 높은데 그 도시들을 잇는 간선의 가중치는 아주 낮고
도시들의 가중치는 아주 낮은데 그 도시들을 잇는 간선의 가중치는 약간 낮고
이 도시들이 섞여 있으면 어떻게 되겠는가? 간선부터 계산해버리면 당연히 잘못된 계산이 된다.
- 최단거리를 구하면서 도시의 가중치의 최대값을 더하기
말로는 아주 그럴듯 하다. 하지만 잘못된 계산이다. 밑 그림을 보자.
출발 도시가 1, 도착 도시가 4라고 생각해보자.
먼저 1번과 3번간 거리를 계산하게 된다.
(1-2-3) = 간선들의 가중치(1 + 1) + 도시의 가중치의 최대값(max(1, 100, 1)) = 102
(1-3) = 간선들의 가중치(50) + 도시의 가중치의 최대값(max(1, 1)) = 51
그러므로 (1-3)이 남게 되고 (1-2-3)은 min 연산으로 인해 1-3으로 덮어진다.
그러면 (1-4)는 자연스럽게 (1-3-4)를 선택하게 된다. 거리는 251.
하지만 (1-2-3-4)는 거리가 203이다. 뭔가 이상하지 않은가?그럼 어떻게 해야 하냐.
도시들의 가중치가 오름차순이 되게끔 정렬하여 그 순서대로 경유지로 하여금 탐색해야 한다.
왜냐하면, 가중치가 제일 큰 것을 거리에 더해서 최단 거리를 구하는 문제이기 때문에, 가중치를 제일 낮은 것부터 시작하여 거리를 갱신해나가야 한다.
플로이드 워셜에서 거리를 갱신하는 과정에서 min 연산을 할 때, 가중치를 더할 때에는 max 연산을 써야 하는데, 만약 가중치가 높은 것부터 시작하면 나중에 가중치가 낮은 것이 들어와도 무시되기 때문.(설명이 이게 맞는건가 싶네)그리고 이동 시간을 담는 행렬, 괴롭히는 시간의 최대값을 담는 행렬을 만들어야 한다.
그래야 min 연산으로 필요한 간선이 덮어지는 사태가 발생하지 않는다.
플로이드 워셜에서 거리를 갱신할 때에는 이동 시간과 괴롭히는 시간을 합쳐서 비교하면 된다.설명을 똑부러지게 하지는 못하겠다.
이 링크와 이 링크를 참고하자.이제 나머지는 코드에 주석을 달았으니 코드를 보면 바로 이해가 갈 것이다.
코드
import sys; input = sys.stdin.readline
from math import inf
N, M, Q = map(int, input().split())
time = list(map(int, input().split())) # 각 도시마다 멍멍이가 원숭이를 괴롭히는 시간
move = [[inf] * N for _ in range(N)] # i -> j 이동 시간
bully = [[inf] * N for _ in range(N)] # i -> j 괴롭힘 시간
for _ in range(M): # 도로 입력
a, b, d = map(int, input().split())
a -= 1; b -= 1 # 도시 번호는 0번부터 시작하게 할 것이므로 1씩 빼자.
move[a][b] = move[b][a] = min(move[a][b], d) # a - b 이동 시간 갱신
bully[a][b] = bully[b][a] = max(time[a], time[b]) # a - b 괴롭힘 시간 갱신
# 괴롭힘 당하는 시간이 제일 짧은 도시부터 경유하면서 플로이드-워셜을 돌리자.
for k, t in sorted(enumerate(time), key = lambda x: x[1]):
move[k][k] = 0 # k -> k 이동 시간은 0
bully[k][k] = t # k -> k 괴롭힘 시간은 k번째 도시의 괴롭히는 시간
for i in range(N):
for j in range(N):
# i -> j 총 시간과 i -> k -> j 총 시간을 비교하여 갱신하자.
if move[i][j] + bully[i][j] > move[i][k] + move[k][j] + max(bully[i][k], bully[k][j]):
move[i][j] = move[i][k] + move[k][j]
bully[i][j] = max(bully[i][k], bully[k][j])
# 질문
for _ in range(Q):
S, T = map(int, input().split())
S -= 1; T -= 1
print(move[S][T] + bully[S][T]) if move[S][T] < inf else print(-1)여담
설명이 많이 힘든 문제였다. 나도 이해를 정확하게 못해서일까..?
결국 이 문제는 경유지의 순서를 임의로 정해야 하는 점이 제일 중요한데, 아마 나도 질문 게시판을 보거나 검색을 해보지 않았다면 지금도 못풀었을 문제인 것 같다.
