[백준] 1956번 : 운동 (Python)

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

 

도시 A에서 시작해서 도시 A로 돌아오는, 사이클을 찾는 문제.

 

import sys

input = sys.stdin.readline

N, M = map(int, input().split()) # 마을의 수 N, 도로의 수 M
distance = [[sys.maxsize]*(N+1) for _ in range(N+1)] # 인접 배열

# 인접 리스트 저장
for i in range(M):
    v, e, w = map(int, input().split())

    distance[v][e] = w # 인접 배열에 그래프 저장

# 플로이드-워셜 
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

# 사이클 찾기
result = sys.maxsize

for i in range(1, N+1):
    result = min(result, distance[i][i]) # 최소 사이클 찾기

if(result == sys.maxsize): # 사이클이 없으면
    print(-1)
else:
    print(result)

 

 

도시 A에서 A로 가는 도로의 길이의 합이 가장 작은 사이클을 찾아야 하는데, 모든 도시를 통과할 필요는 없다.

즉, 도시 A에서 B로 갔다가 A로 돌아오는 것도 가능!

 

 

 [문제풀이]

---

 

이러한 사이클을 찾으려면 모든 도시에서 자신 포함 다른 모든 도시로 가는 최단 거리를 구해야 한다.

즉, 플로이드-워셜 알고리즘을 사용해야 한다.

 

이때 출발한 마을-> 도착 마을의 최단 거리를 계산해야 하므로 0을 넣어주지 않는다.

distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

 

그럼 distance[i][i]에 사이클을 이루는 최단거리들이 저장된다. 그 거리 중에 가장 최소인 사이클을 찾으면 된다.

for i in range(1, N+1):
    result = min(result, distance[i][i]) # 최소 사이클 찾기

 

 

플로이드 워셜의 시간 복잡도는 O(N^3)이지만 N이 400이므로 충분히 충족하는 시간이다.

다만.. 파이썬은 너무 느려서 원래는 되야하지만 시간 초과가 난다....

PyPy3으로 할 것!