[Python/파이썬] 백준 알고리즘 1956번 - 운동 (변형된 다익스트라/Dijkstra) (feat. 플로이드)

 

 

 

<풀이>

처음에는 플로이드로 풀었다.

"""
1. 아이디어
- 플로이드로 전체 마을 사이의 최단 경로를 구한다.
    - 이중 for문으로 도로의 길이의 합이 가장 작은 사이클을 찾는다.

2. 시간 복잡도
- O(V^3 + V^2) : 400 ^ 3 ~= 6억

3. 변수
- V, E : int
- dist : int[][]
- min_dist : int
"""
import sys
INF = sys.maxsize

input = sys.stdin.readline

V, E = map(int, input().split())

dist = [[INF] * (V + 1) for _ in range(V + 1)]

for l in range(1, V + 1):
    dist[l][l] = 0

for _ in range(E):
    a, b, c = map(int, input().split())
    dist[a][b] = min(dist[a][b], c)

for k in range(1, V + 1):
    for i in range(1, V + 1):
        for j in range(1, V + 1):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

min_dist = INF
for a in range(1, V + 1):
    for b in range(1, V + 1):
        if a != b and dist[a][b] < INF - 1 and dist[b][a] < INF - 1:
            if min_dist > dist[a][b] + dist[b][a]:
                min_dist = dist[a][b] + dist[b][a]

if min_dist > INF - 1:
    print(-1)
else:
    print(min_dist)

풀기전 시간 복잡도를 계산해 봤을 때 6억 가까이 나와 안되겠다는 생각은 들었다.

하지만 다익스트라로 계산하면 시간이 더 걸린다고 단순히 생각해 그냥 일단 플로이드 와샬 알고리즘으로 접근하였다.

결과적으로 Pypy3로는 맞았으나 Python3로는 시간초과가 나왔다.

 

문제의 조건에 맞는 해결을 위해선 새로운 접근이 필요했다.

이는 다익스트라의 변형으로 해결할 수 있었다.

 

필자가 첫 접근에서 다익스트라가 더 시간이 오래걸린다고 예상한 이유는 플로이드 풀이는 O(V^3)의 시간 복잡도를 갖지만 다익스트라로 모든 노드에서 출발한 가지수를 구하는 시간 복잡도는 O(ElgV * V) = O(V^3lgV)로 플로이드의 풀이보다 lgV를 곱한 만큼 더 걸린다고 생각했기 때문이다. (E는 최대 V^2가 될 수 있기 때문)

 

하지만 이 문제에서는 최단 경로 "사이클"을 구하므로 heap 자료구조를 이용한 다익스트라 알고리즘에서는 E가 V^2가 되기 전에 최소 사이클을 구해 while문을 탈출할 수 있었다.

(heap을 이용하기 때문에 처음 나온 사이클이 가장 비용이 작은 사이클이므로)

 

이에 대한 풀이는 아래와 같다.

"""
1. 아이디어
- 다익스트라를 변형하여 이용한다.
    - heap에 출발 노드까지 포함된 요소들로 초기 값에 가능한 모든 edge들을 넣어놓고 시작한다. (ElgV)
    - while문에 break를 추가해 소요 시간을 줄일 수 있도록 한다.

2. 시간 복잡도
- O(ElgV) : V^2 * lgV = 400^2 * lg(400) ~= 400,000      -> 가능

3. 변수
- V, E : int
- heap : (거리, 출발 마을, 도착 마을)
- 인접 리스트 : (거리, 도착 마을)
- 최단 거리 : int[][]
"""
import sys
import heapq
INF = sys.maxsize

input = sys.stdin.readline

V, E = map(int, input().split())

dist = [[INF] * (V + 1) for _ in range(V + 1)]  # 사이클을 구해야하므로 자기 자신한테 가는 최단거리를 0으로 세팅해두지 않음

heap = []
edge = [[] for _ in range(V + 1)]
for _ in range(E):
    a, b, c = map(int, input().split())
    dist[a][b] = min(dist[a][b], c)
    edge[a].append([c, b])
    heapq.heappush(heap, [c, a, b])

while heap:
    w, s, g = heapq.heappop(heap)
    if s == g:
        print(w)
        break
    if w != dist[s][g]: continue
    for nw, ng in edge[g]:
        if dist[s][ng] > dist[s][g] + nw:
            dist[s][ng] = dist[s][g] + nw
            heapq.heappush(heap, [dist[s][ng], s, ng])
else:
    print(-1)

기존의 다익스트라 알고리즘과 다른 점은 heap에 요소를 추가할 때 출발 노드의 정보도 함께 넣는다는 것이다.

그리고 초기 heap의 값에 전체 edge를 다 넣어두고 if문을 통해 (if s == g) 싸이클이 만들어지는 경우 break로 탈출함으로써 시간 소요를 줄였다.

이를 통해 기존의 다익스트라 알고리즘으로 전체 각 노드간의 시간 복잡도를 O(V^3lgV)에서 O(ElgV)로 줄일 수 있었다.

 

 

 

<핵심 정리>

1. 다익스트라의 변형으로도 플로이드 문제를 풀 수 있다.

2. 시간 복잡도상 해결이 제한 시간내에 해결이 어렵다면 다른 방법을 먼저 생각해보자.

3. 위 문제에서 다익스트라 알고리즘이 더 빠를 수 있었던 건 싸이클을 구하는 조건이 있었기 때문이다. 이 덕에 break문으로 더 적은 간선만을 확인할 수 있었다.