[22동계모각코] 8회 계획 및 평가

시작 시간 : 23-01-31 오후 6시

오늘의 목표

• 플로이드-워셜 알고리즘 공부

---

플로이드 워셜 알고리즘이란?

모든 노드에서 다른 모든 노드까지 이동하는 최소비용을 구하는 알고리즘이다.

기본 동작은 다익스트라 알고리즘과 비슷하다고 느꼈다.

A에서 B까지 이동하는 것보다 A와 B 사이에 k를 지나 도달하는 게 더 저렴한 비용으로 도달할 수 있다는 점에서 이 알고리즘이 만들어진 듯했다.

이 알고리즘은 정해진 점화식에 따라 비용이 수정된다는 점에서 다이나믹 프로그래밍에도 속한다고 한다.

• D_ab = min(D_ab, D_ak + D_kb)
• D_ab : a에서 b로 가는 거리(distance)

---

시간복잡도🕐

입력 노드가 N개 일때, 모든 노드에 대해서 다른 모든 노드(N개)로 가는 경로를 탐색한다. 그렇기 때문에 출발 노드와 도착 노드에 대해서만 따지면 2중첩 반복문으로 N^2 이 된다. 하지만 우리는 중간에 k를 지나는 경로에 대해서 모두 탐색해보아야 한다. 그러므로 시간 복잡도는 O(N^3)이다.

따라서 입력의 크기를 잘 확인하고 사용해야 한다. N이 1,000을 넘어가게 되면 N^3은 1,000,000,000 (10억)이 된다. 이는 주어진 시간 내에 프로그램이 동작하기 버거울 수 있으므로 잘 판단하고 쓰자. 내가 보았던 강의에서는 보통 입력 크기가 500이하(이면서 제한시간은 1초 이내)인 경우에서 사용한다고 한다.  (500^3 = 125,000,000)

---

구현👀

이번 알고리즘은 유튜브 강의 동영상을 보며 개념을 익혔다. 그래프는 어제 공부한 다익스트라와 동일한 그래프를 사용할 생각이다.

# 출발노드 : (도착노드, 비용)
graph = {1: [(2, 2), (3, 5), (4, 1)],
         2: [(3, 3), (4, 2)],
         3: [(2, 3), (6, 5)],
         4: [(3, 3), (5, 1)],
         5: [(3, 1), (6, 2)],
         6: []}

INF = 10 ** 8  # 상수, 무한대를 의미
n = len(graph)

distances = [[INF] * n for _ in range(n)]

# 자신부터 자신까지의 거리는 모두 0으로 초기화
for a in range(n):
    for b in range(n):
        if a == b:  distances[a][b] = 0

# 출발 노드와 이어져 있는 도착 노드들에 대한 비용을 초기화 해준다.
# 이렇게 초기화를 해주는 작업이 없으면 제대로 동작하지 않는다.
for start in graph:
    for destination, cost in graph[start]:
        distances[start - 1][destination - 1] = cost

for k in range(n):
    for a in range(n):
        for b in range(n):
            # if distances[a][b] == 0: continue #--> 필요없는 코드. 어차피 0이하의 수가 없으므로 점화식에선 어차피 0이 채택됨.
            distances[a][b] = min(distances[a][b], distances[a][k] + distances[k][b])

for a in range(n):
    for b in range(n):
        if distances[a][b] == INF:
            print("INF", end=" ")
        else:
            print(distances[a][b], end=" ")
    print()

>> 0 2 3 1 2 4 
>> INF 0 3 2 3 5 
>> INF 3 0 5 6 5 
>> INF 5 2 0 1 3 
>> INF 4 1 6 0 2 
>> INF INF INF INF INF 0

---

어째서 INF가 나왔나💦

출력 결과를 살피면 INF가 있음을 확인할 수 있다. 결론부터 말하면 INF라고 나타난 이유는 출발노드에서 해당 순번 노드로 이동하지 않아 비용 정보가 업데이트되지 않았기 때문이다.

첫 번째 행을 제외한 모든 행들의 각 출력의 첫 번째 열은 INF를 출력한다. 1번을 제외하곤 다른 노드들은 1번 노드로 이동할 방법이 없기 때문에 INF가 다른 값으로 업데이트되지 않았던 것이다.

6번째 행의 6열 값을 제외하곤 모두 INF 이유도 마찬가지이다. 다른 노드로 이동하지 않으므로 INF가 업데이트되지 않은 것이다.

---

두 번의 초기화를 하는 이유

위 코드는 초기화 작업을 두 번씩이나 해주는 중이다. 그 이유는 graph가 dictionary 이기 때문이다. 딕셔너리이기 때문에 A>>B 는 있지만 B>>A가 존재하지 않는 경우 굳이 표현해줄 필요가 없다. 그런데 오히려 이런 상황이 시간을 더 지연시키고 있는 실정이다. 그래서 플로이드 워셜 알고리즘을 사용할 땐 두 번의 초기화를 하지 않게끔 graph 자체를 2차원 배열로 나타내는 편이 좋겠다는 생각이다.

---

 

+ 오늘 학습한 알고리즘으로 백준에서 문제를 풀었다.