✏️ 서론
이번시간에는 최단경로의 마지막 개념인 플루이드 워셜 알고리즘(floyed_warshall_algorithm)을 배워보자.
✏️ 본론
📍 플로이드 워셜 알고리즘
참고한 강의
어제 결론을 이어 다익스트라 알고리즘과 플로이드 워셜의 차이점을 자세히 알아보자.
| 구분 | 다익스트라(heap) | 플로이드워셜 |
|---|---|---|
| 사용시기 | 한 지점에서 다른 특정 지점까지의 최단경로를 구하는 경우 | 모든 지점에서 다른 모든 지점까지의 최단경로를 구하는 경우 |
| 핵심원리 | 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾음 | 방문하지 않은 노드 중 최단거리를 갖는 노드를 찾지 않음 |
| 리스트 | 1차원 | 2차원 |
| 분류 | 그리디(greedy) | 다이나믹프로그래밍(dp) |
| 시간복잡도 | O(ElogV) | O(N^3) |
| 입력범위 | N >= 30,000 | N <= 5,000 |
플로이드워셜 알고리즘의 각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다.
예를 들어, 2번 노드의 점화식을 구할 때 대각선과 2행 2열의 값은 구하지 않아도 된다.
즉, [1, 2, 3, 4]의 노드 중 2를 제외한 나머지 [1, 3, 4]노드 중 2개의 노드를 뽑는 경우 [1, 3], [1, 4], [3, 1], [3, 4], [4, 1], [4, 3]의 경우의 수만 구하면 된다.
나머지 노드의 경우의 수를 구할때도 동일하다.
다음 코드는 3개의 data 중 2개를 뽑는 경우의 수를 출력한 코드이다.
만약, 다음으로 어떤 항을 구해야하는지 헷갈린다면 참고해서 사용하자.
import itertools
data = [1, 3, 4]
for i in itertools.permutations(data, 2):
print(list(i), end=' ')
👉🏽 [1, 3] [1, 4] [3, 1] [3, 4] [4, 1] [4, 3]위에서 설명한 2번 노드의 점화식을 구할 때는 다음과 같이 표로 쉽게 나타낼 수 있다.
대각선과 2행과 2열이 포함된 행열은 계산을 하지 않고, 연필로 표시한 부분만 계산하면되는데 이는 방금 permutations_code처럼 경우의 수가 6인 것과 동일하다.
| 출발/도착 | 1번 | 2번 | 3번 | 4번 |
|---|---|---|---|---|
| 1번 | 0 | * | ✏️ | ✏️ |
| 2번 | * | 0 | * | * |
| 3번 | ✏️ | * | 0 | ✏️ |
| 4번 | ✏️ | * | ✏️ | 0 |
한가지 예를 더 들어 노드 3을 구할때는 다음과 같이 구하면 된다.
| 출발/도착 | 1번 | 2번 | 3번 | 4번 |
|---|---|---|---|---|
| 1번 | 0 | ✏️ | * | ✏️ |
| 2번 | ✏️ | 0 | * | ✏️ |
| 3번 | * | * | 0 | * |
| 4번 | ✏️ | ✏️ | * | 0 |
1~4번까지 모든 경우의 수를 구했다면 다음과 같은 테이블이 나온다.
| 출발/도착 | 1번 | 2번 | 3번 | 4번 |
|---|---|---|---|---|
| 1번 | 0 | 4 | 8 | 6 |
| 2번 | 3 | 0 | 7 | 9 |
| 3번 | 5 | 9 | 0 | 4 |
| 4번 | 7 | 11 | 2 | 0 |
참고로, 플로이드 워셜의 점화식은 다음과 같다.
D(ab) = min(D(ab), D(ak) + D(kb))
소스코드로 나타내면 다음과 같다.
'''
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
'''
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
print(graph)
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 a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b] == INF:
print('INFINITY', end= ' ')
else:
print(graph[a][b], end=' ')
print()
👉🏽
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0📍 [ 문제 1 ] 미래도시
문제는 나동빈 - 최단경로에서 찾을 수 있다.
문제요약: 1번회사에서 출발해 X를 거쳐 K로 가는 최단거리를 구하라.
전형적인 플로이드워셜 알고리즘 문제인데, 주어진 입력 값의 범위가 100이하로 매우 한정적이기때문에 떠올릴 수 있었다.
핵심 아이디어는 1번에서 X를 거쳐야 하기 때문에 이 구간의 최단거리와 X에서 K로 갈때의 최단거리를 더해주면된다.
short_distance = graph[1][x] + graph[x][k]
중간에 헷갈린게 있었는데, x와 k는 첫 for문에서 받지말고 중간에서 input값으로 받아주자.
'''
5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5
4 2
1 3
2 4
3 4
'''
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
for i in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
x, k = map(int, input().split())
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])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print(-1)
else:
print(distance)
👉🏽 3
-1📍 [ 문제 2 ] 전보
마찬가지로 문제는 나동빈 - 최단경로에서 찾을 수 있다.
문제요약: 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇개이며, 도시들이 모두 메시지를 받는데까지 걸린 시간은 얼마인지 계산하시오.
우선순위(heap) 다익스트라로 풀어야겠다는 생각을 했는데, 이유는 N, M값이 충분히 크고, 한 도시에서 다른 도시까지의 최단거리 문제로 치환할 수 있기 때문이다.
그런데, 모든 도시들이 메시지를 받는데까지 걸리는 시간을 구해야하기 때문에 도달이 가능한 도시 중 가장 큰 비용(max) 값을 구해야한다.
이 부분을 어떻게 해결할지몰라 고민했다.
max_distance라는 변수를 설정하고 반복문을 설정하여 기존 distance의 i값을 비교하여 제일 큰 수를 넣어주었다.
그리고, 문제에서 도시 C에서 보낸 메세지를 받는 도시의 총 개수라고 했으니까 C를 제외하고 메세지를 받은 도시를 나열해야한다 그러므로, 총 count에서 -1을 해줬다.
'''
3 2 1
1 2 4
1 3 2
'''
import heapq
INF = int(1e9)
n, m, start = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
for i in range(m):
x, y, z = map(int, input().split())
graph[x].append((y,z))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
max_distance = 0
count = 0
for i in distance:
if i != INF:
count += 1
max_distance = max(max_distance, i)
print(count - 1, max_distance)
👉🏽 2 4✏️ 결론
이 외에도 플로이드워셜알고리즘은 문제가 많지만 하나푸는데 오래걸려 많은 문제를 풀진 못했다.
어느덧 이 책의 이론 부분의 마지막 파트인 그래프 이론만을 남겨두고 있다.
알고리즘 공부를 한지 27일밖에 되지않아 이제 감을 조금 익혔다?라는 생각이든다.
이론을 공부하고 알고리즘 문제를 풀면 더 가까이 느껴지지 않을까?
화이팅.
