[백준 1956 파이썬] 운동 (골드 4, 플로이드 워셜)

알고리즘 유형 : 플로이드-워셜(최단 경로)
풀이 참고 없이 스스로 풀었나요? : △

https://www.acmicpc.net/problem/1956

소스 코드(파이썬)

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

V, E = map(int, input().split())
APSP = [[INF]*(V+1) for _ in range(V+1)]

for i in range(1, V+1):
    APSP[i][i] = 0

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

# 플로이드-워셜 알고리즘
def floyd_warshall():
    for mid in range(1, V+1):
        for start in range(1, V+1):
            for end in range(1, V+1):
                cal_dist = APSP[start][mid] + APSP[mid][end]
                
                if cal_dist < APSP[start][end]:
                    APSP[start][end] = cal_dist
    return APSP

APSP = floyd_warshall()

result = INF
# 모든 노드에 대해 최단 사이클 구하기
# 사이클을 구하는 방법은, 예를 들어
# 1에서의 사이클을 구하고 싶다면
# 1의 인접 노드 a, b, c로 이동한 다음
# a, b, c에서 1까지 최단 거리로 이동한다.
# 1 -> a - > 1, 1 -> b -> 1, 1 -> c -> 1
# 이 중 최솟값이 1에서의 최단 사이클이다.
# 이런 식으로 모든 노드들에 대해 수행해주는 것이다.
for c_villege in range(1, V+1):
    for adc_villege in range(1, V+1):
        if c_villege != adc_villege:
            cycle = APSP[c_villege][adc_villege] + APSP[adc_villege][c_villege]
            result = min(result, cycle)

if result >= INF:
    print(-1)
else:
    print(result)

풀이 요약

1. 플로이드-워셜 알고리즘으로 풀면 pypy3으로 제출해야 통과된다. 다익스트라를 활용하여 풀 수도 있는데, 더 오래 걸리길래 시간복잡도를 비교해봤는데 다익스트라는 노드 수만큼 실행해줘야하니까 2VElogV, 문제의 조건에서 E의 범위가 V^2-V 까지랬으니 대충 V^3logV 정도 되겠다. 플로이드-워셜은 V^3이니 이렇게 비교해보면 다익스트라 풀이가 더 오래 걸리는게 맞다.

   다익스트라를 변형하여 python3으로도 통과되는 풀이가 있는데 이 풀이는 검색을 통해 다른 블로그에서 참고하시면 좋을 것 같네요

2. 우선 플로이드 워셜로 APSP 리스트를 구한다.

3. 테스트케이스를 예로 들면, 1에서의 사이클, 2에서의 사이클, 3에서의 사이클 값을 모두 구한 뒤 이 중 최소값을 출력해야한다.

   1에서의 사이클을 구해보자.

   사이클을 구하는 방법은, 1에서 인접노드 P로 이동한 다음 그 인접노드에서 1로 가는 최단 거리 값을 더한 것이 사이클 값이다.

   즉, 1에서의 사이클 값은 1의 인접 노드가 a, b, c 라고 할 때

   1 -> a -> 1
   1 -> b -> 1
   1 -> c -> 1

   이 중 최솟값이다.

4. 이 것을 이중 for문을 통해 모든 노드 쌍에 대해 수행해주면 그래프 전체에 대한 최단 사이클을 찾을 수 있다.

   이 때 인접 노드들 뿐만 아닌 모든 노드들을 대상으로 찍고 돌아오게 for문을 짠 이유는, 만약 인접 노드가 아닌 노드의 최단 거리 값이 INF라고 해도, cycle 값을 갱신할 때 min 함수를 취하므로 올바른 값이 정상적으로 채택될 수 있게 된다.

배운 점, 어려웠던 점

• 플로이드-워셜 알고리즘이 가물가물해서 다시 개념을 찾아봤다. 아직 경험이 많이 부족한 것 같다.