백준 1956번 : 운동 in Python

1956번: 운동

 

www.acmicpc.net

이 문제는 그래프 내에서 최단 사이클을 구하는 문제이다.

우선 어떤 점에서 시작하는 사이클을 찾으려면 그 점을 시작점으로 하는 최단 경로를 찾되 시작점 역시 목적지 후보로 두어야 한다. 그리고 그래프 내에서 모든 사이클을 고려하려면 모든 점에 대해 그 점을 시작점으로 해 최단 경로를 생각해야 한다. 그래서 Dijkstra 알고리즘이 아닌 Floyd-Warshall 알고리즘을 이용하는 것이 시간 면에서 더 효율적이다. 

이후 이를 구현하는 것은 이전의 플로이드 문제와 동일하지만 앞에서 언급했던 대로 시작점 역시 목적지 후보로 두어야 한다. 그래서 초기에 행과 열이 같은 지점의 값을 0으로 두지 않는다. 그 점 이외에는 기존의 Floyd-Warshall 알고리즘과 동일하다. 이를 수행한 뒤 가장 짧은 사이클을 구해야 하므로 행과 열이 같은 entry들 중 최소값을 찾는다.

이를 코드로 구현하면 다음과 같다.

import sys
V, E = map(int, input().split())
graph = [[sys.maxsize]*(V+1) for _ in range(V+1)]
for _ in range(E):
    a, b, c = map(int, input().split())
    graph[a][b] = c
# 기존의 Floyd-Warshall 알고리즘과 달리 graph[i][i] = 0 부분이 없다.
for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
res = sys.maxsize
# 사이클 중 가장 길이가 짧은 사이클을 찾는다.
for i in range(1, V+1):
    res = min(res, graph[i][i])
# 사이클이 없는 경우 -1을 출력한다.
if res == sys.maxsize:
    print(-1)
else:
    print(res)