[백준/파이썬] 1956 : 운동

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

1956번: 운동

문제 요약 : V개의 마을과 E개의 일방 통행 도로가 있다. 최소 사이클의 도로 길이 합을 출력하라. 불가능할 경우에는 -1을 출력하라.
 
 
다 풀어놓고 한참을 고생했다.
알고보니, INF값을 나름대로 큰 값을 준다고 변수들의 값을 참고해서 지정했는데, 거기부터 잘못된 시도였다..
 
V의 범위가 0부터 400사이였고, E의 범위가 V 보다 작거나 같았기 때문에 INF를 500으로 주었다.
그런데 이 INF값은 사이클이기 때문에 한 노드만 지나는 게 아닌 여러 노드를 지날 수 있다...ㅋㅋㅋㅋㅋ
진짜 이거 알고 얼마나 허탈했는지 바부..🤦‍♀️ 
INF값을 sys.maxsize로 주고 문제를 끝낼수 있었다..
 
 
 

풀이 )

플로이드 워셜 알고리즘을 이용한 문제!
플로이드 워셜에 대한 설명은 요기에!!

[알고리즘/Python] 플로이드-워셜(Floyd-Warshall) 알고리즘

다익스트라 알고리즘을 이용하여서도 풀 수 있다고 한다.
 
플로이드 워셜 알고리즘을 이용한 이유는, 모든 노드 간의 최단거리를 구할 수 있기 때문이다.
출발점이나 도착점이 정해져 있지 않고, 그냥 '최단거리의 사이클'만 구하면 되기 때문이다.
원래 플로이드 워셜 알고리즘은 출발과 도착이 같은 노드는 0의 값을 가지겠지만, INF값을 주어 사이클을 구할 수 있게 하였다.
그리하여 출발도 도착이 같은 노드들 간에 최소값을 구하여 출력하였다.

# 운동
import sys
input = sys.stdin.readline

V, E = map(int,input().split(' '))
INF = sys.maxsize
town = list(list(INF for _ in range(V+1)) for _ in range(V+1))


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

for k in range(1,V+1):
    for i in range(1,V+1):
        for j in range(1,V+1):
            town[i][j] = min(town[i][j], town[i][k]+town[k][j])


answer = INF
for v in range(1,V+1):
    answer = min(answer, town[v][v])

if answer == INF :
    answer = -1

print(answer)

그래도 고민을 한시간 가량만 해서 너무 다행이다..^_ㅠ
PyPy로 푼 이유는 Python에서는 시간초과가 났기 때문이다. Python에서 사용하려면 다익스트라 알고리즘을 사용해야하는 듯 하다.