[Python] 백준 1956 운동

1. 문제 링크

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

1956번: 운동

2. 문제 요약

최소 사이클의 도로 길이의 합을 출력한다.

---

3. 아이디어 정리

1. 모든 정점에서 모든 정점으로 가는 최소 거리 구하기 ⇒ 플로이드 와샬
2. 자기 자신 -> 자기 자신 마을로 돌아오는 거리 중 최솟값 구하기

참고 - 플로이드와샬

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.

 

플로이드 워셜 점화식

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

• a에서 b로 가는 최단 거리, a에서 k를 거쳐 b로 가는 거리 비교

---

4. 문제 풀이

4-1. 내 풀이

import sys
INF = int(1e9)

v, e = map(int, sys.stdin.readline().split()) # v개의 마을, e개의 도로

# 2차원 그래프, 모든 값을 무한으로 초기화
graph = [[INF] * (v + 1) for _ in range(v + 1)]   # 거리를 담는 테이블

# a -> b 마을 가는 도로 길이를 c로 넣기
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = c

# 1. 모든 정점에서 모든 정점으로 가는 최소 거리 구하기
for k in range(1, v + 1):
    for a in range(1, v + 1):   # 출발 노드
        for b in range(1, v + 1):   # 도착 노드
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 2. 자기자신 -> 자기자신 마을로 돌아오는 거리 중 최소값 구하기
result = INF
for i in range(1, v + 1):
    result = min(result, graph[i][i])

if result == INF:
    print(-1)
else:
    print(result)

 

---

5. 결론

• 플로이드 와샬을 이용하면 쉽게 풀리는 문제이다.