[Python/백준] 운동

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

 

---

저는 노드가 400개이기 때문에

400 ^ 3이 1억번보다 적어 플로이드 워셜 알고리즘을 사용해야겠다고 생각했습니다

 

import sys
input = sys.stdin.readline
INF = int(1e9)

v, e = map(int, input().split())

graph = [[INF]*(v+1) for _ in range(v+1)]

for i in range(1, v+1):
    graph[i][i] = 0
    
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a][b] = c # 단방향
    
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])
 
mini = INF
for i in range(1, v+1):
    for j in range(1, v+1): 
        if i==j:
            continue
        a = graph[i][j]
        b = graph[j][i]
        if a == INF or b == INF:
            continue
        mini = min(mini, a+b)
        
print(mini if mini != INF else -1)

하지만 이렇게 했을 때 시간 초과가 났습니다(PyPy3으로는 풀림)

 

그래서 방법을 찾던 와중

'최소 사이클 구하기' 에서는 자기 자신으로 가는 경로를 INF 로 두고 시작하면 더 쉽게 풀 수 있다는 글을 봤습니다.

 

최소 사이클

출발지에서 다시 출발지로 돌아오는 경로(사이클) 중 최소 거리를 구하는 것

 

예를 들어 출발점 1에서 1로 돌아오는 사이클을 알고 싶다면 INF 로 초기화를 해야 한다는 것입니다.

0으로 초기화한다면 이미 0이므로 사이클을 알 수 없습니다.

INF로 초기화한다면 사이클이 생겼을 때 다른 값으로 바뀌는 것입니다.

 

 

• 사이클이 없는 경우: 자기 자신으로 가는 거리를 INF로 설정하면, 사이클이 존재하지 않는 경우 그 값은 여전히 INF로 남아있게 됩니다. 즉, 출발지로 돌아오는 경로가 없는 것이므로, 사이클이 없다는 것을 알 수 있습니다.
• 사이클이 있는 경우: 만약 노드 i에서 시작해 다시 노드 i로 돌아오는 경로(사이클)가 존재하면, 플로이드-워셜 알고리즘을 통해 그 경로의 최소 거리가 계산됩니다. 플로이드-워셜은 모든 노드 간 최단 거리를 계산하는 알고리즘이므로, 이 과정에서 자기 자신으로 돌아오는 경로도 최적화됩니다. 결과적으로, city[i][i]에 들어있는 값이 그 노드에서 출발해 다시 돌아오는 최소 사이클의 거리가 됩니다.

 

import sys
input = sys.stdin.readline
INF = int(1e9)

v, e = map(int, input().split())

graph = [[INF]*(v+1) for _ in range(v+1)]
    
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a][b] = c # 단방향
    
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])
 
mini = INF
for i in range(1, v+1):
    if graph[i][i] != INF:
        mini = min(mini, graph[i][i])
        
print(mini if mini != INF else -1)

물론 이 풀이도 python에서는 시간초과가 나지만,

후에 사이클을 확인할 때 2중 반복문이 아닌 1중으로 확인이 가능합니다!