[python/백준] 1956번: 운동

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

1956번: 운동

 

 

⭐ 문제

 

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

 

 

 

⭐ 코드 분석

 

플로이드 와샬 알고리즘

모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성합니다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복합니다

 

>>> 플로이드 와샬 알고리즘은 선택지 중 가장 짧은 선택만을 반복하여 결과값을 얻는 알고리즘으로 구문을 실행하기 전에 모든 값을 무한으로 만들고 구문을 실행해야한다

 

 

가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9를 이용할 수 있음
1e9 = 1*109 = 1000000000,
2e9 = 2*109 = 2000000000

 

 

⭐ 코드

 

 

<pypy>

import sys
INF = int(1e9)

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

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

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

# 모든 정점에서 모든 정점으로 가는 최소 거리
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])

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

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

 

 

<python3>

import sys

# 전처리 부분
input = sys.stdin.readline
INF = sys.maxsize

# 알고리즘 부분
def floyd():
    for i in range(1, v + 1):
        for j in range(1, v + 1):
            for k in range(1, v + 1):
                if dist[j][k] > dist[j][i] + dist[i][k]:
                    dist[j][k] = dist[j][i] + dist[i][k]

# 변수 선언 및 초기화 부분
v, e = map(int, input().split())
dist = [[INF] * (v + 1) for _ in range(v + 1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    dist[a][b] = c    

# 메인 코드 부분
floyd()

ans = INF
for i in range(1, v + 1):   
    ans = min(ans, dist[i][i])  # 사이클은 출발점과 도착점이 같은 경우를 의미

print(ans if ans < INF else -1)