[백준] 1956번: 운동 Python (플로이드-워셜)

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

1956번: 운동

pypy 로 제출해서 맞은 코드 

플로이드워셜이라는 힌트를 가지고 풀었다. 
처음에는 Union-find 로 사이클을 찾아야 하는가? 라고 생각했으나, 결국 문제에서는 최소 경로 비용을 구하는 것이 핵심이므로 플로이드 워셜로 푸는것이 더 적절하다고 판단했다. 

우선,graph 구성했다.  예제를 기준으로 아래의 graph를 만들어 보았다.
graph 에는 a-> b 가는 경로의 비용을 저장한다. 자기자신 노드에서 자기자신노드로 가는 경우 0 으로 초기화한다. 갈 수 없는 경로의경우 INF 값을 저장해서 경로가 없음을 표시했다. 

우선 플로이드 워셜 알고리즘으로 i -> j 지점까지의 최소 경로를 구해서 graph 에 저장했다. 

for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])

graph 테이블에 저장한 최소경로를 이용해서 cycle이 생성되는 경우를 찾아주었다.

단, i == j == k 의 경우 자기자신 노드 to 자기자신 노드 가 되어버리므로 이 경우를 제외시켰다.
그리고 i to k 또는 k to j, j  to k 또는 k to i 경로 비용이 INF라는 것은 갈 수 없다는 것을 의미하므로 이 경우도걸러주었다. 

for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            if not (i == j == k):
                if graph[i][k] != INF and graph[k][j] != INF and graph[j][k] != INF and graph[k][i] != INF:
                    temp = graph[i][k] + graph[k][j] + graph[j][k] + graph[k][i]
                    answer = min(temp, answer)

 

전체 코드 

import sys

input = sys.stdin.readline

INF = int(1e9)
v, e = map(int, input().split())
answer = INF

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

for i in range(1, v+1):
    for j in range(1, v+1):
        if i == j:
            graph[i][j] = 0 # 자기 자신 to 자기 자신

for i in range(e):
    a, b, cost = map(int, input().split())
    graph[a][b] = cost

for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])

for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            if not (i == j == k):
                if graph[i][k] != INF and graph[k][j] != INF and graph[j][k] != INF and graph[k][i] != INF:
                    temp = graph[i][k] + graph[k][j] + graph[j][k] + graph[k][i]
                    answer = min(temp, answer)
                    
if answer == INF:
    print(-1)
else:
    print(answer)