[백준 1956번] 파이썬 - 운동

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

1956번: 운동

 

 

 

# 조건

• V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다.
• 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다.
• 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
• 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다.
• 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다.
  • 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
• 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오.
• 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

 

입력

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

 

# 접근 방법

• 모든 노드 간에 최단 경로를 탐색해야하므로 플로이드 워셜알고리즘을 이용해준다.
  • 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다.
  • 그래프를 인접 행렬로 표현한다.
• 아래와 같은 점화식을 도출 할 수 있다.
  • D [S] [E] = Math.min(D [S] [E], D [S] [K] + D [K] [E] )
• 3중 FOR문을 이용하므로 O(V^3)의 시간복잡도를 가진다.
  • 400^3 = 64,000,000 이라서 2초가 넘을 수도 있지만, 다익스트라의 경우 노드마다 돌아야 하므로 플로이드 워셜의 시간복잡도가 조금 더 맞는 것 같다.

 

참고 - 플로이드 워셜
https://cheon2308.tistory.com/entry/Algorithm-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
INF = sys.maxsize  
  
def floyd():  
    # 경유지 k에 관해  
    for k in range(1, V+1):  
        # 출발노드 s에 관해  
        for s in range(1, V+1):  
            # 도착노드 E에 관해  
            for e in range(1, V+1):  
                if dist[s][e] > dist[s][k] + dist[k][e]:  
                    dist[s][e] = dist[s][k] + dist[k][e]  
  
    return dist  
  
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  
  
result = floyd()  
min_dist = INF  
# 자기 자신으로 돌아오는 값 중 최소 값 출력  
# 경로가 불가능한 경우 -1 출력  
for i in range(1, V+1):  
    for j in range(1, V+1):  
        if i == j:  
            if dist[i][j] < min_dist:  
                min_dist = dist[i][j]  
  
print(min_dist if not min_dist == INF else -1)