알고리즘 유형 : 플로이드-워셜(최단 경로)
풀이 참고 없이 스스로 풀었나요? : △
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)풀이 요약
-
플로이드-워셜 알고리즘으로 풀면 pypy3으로 제출해야 통과된다. 다익스트라를 활용하여 풀 수도 있는데, 더 오래 걸리길래 시간복잡도를 비교해봤는데 다익스트라는 노드 수만큼 실행해줘야하니까 2VElogV, 문제의 조건에서 E의 범위가 V^2-V 까지랬으니 대충 V^3logV 정도 되겠다. 플로이드-워셜은 V^3이니 이렇게 비교해보면 다익스트라 풀이가 더 오래 걸리는게 맞다.
다익스트라를 변형하여 python3으로도 통과되는 풀이가 있는데 이 풀이는 검색을 통해 다른 블로그에서 참고하시면 좋을 것 같네요
- 우선 플로이드 워셜로 APSP 리스트를 구한다.
-
테스트케이스를 예로 들면, 1에서의 사이클, 2에서의 사이클, 3에서의 사이클 값을 모두 구한 뒤 이 중 최소값을 출력해야한다.
1에서의 사이클을 구해보자.
사이클을 구하는 방법은, 1에서 인접노드 P로 이동한 다음 그 인접노드에서 1로 가는 최단 거리 값을 더한 것이 사이클 값이다.
즉, 1에서의 사이클 값은 1의 인접 노드가 a, b, c 라고 할 때
1 -> a -> 1
1 -> b -> 1
1 -> c -> 1이 중 최솟값이다.
-
이 것을 이중 for문을 통해 모든 노드 쌍에 대해 수행해주면 그래프 전체에 대한 최단 사이클을 찾을 수 있다.
이 때 인접 노드들 뿐만 아닌 모든 노드들을 대상으로 찍고 돌아오게 for문을 짠 이유는, 만약 인접 노드가 아닌 노드의 최단 거리 값이 INF라고 해도, cycle 값을 갱신할 때 min 함수를 취하므로 올바른 값이 정상적으로 채택될 수 있게 된다.
배운 점, 어려웠던 점
- 플로이드-워셜 알고리즘이 가물가물해서 다시 개념을 찾아봤다. 아직 경험이 많이 부족한 것 같다.
