BAEKJOON #1956 운동 (다익스트라) - python

nathan·2021년 11월 5일

알고리즘문제

목록 보기

84/102

운동

출처 : 백준 #1956

시간 제한	메모리 제한
2초	192MB

문제

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) 쌍이 같은 도로가 여러 번 주어지지 않는다.

출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

입출력 예시

예제 입력 1

3 4
1 2 1
3 2 1
1 3 5
2 3 2

예제 출력 1

3

풀이

생각

최단경로를 구하는 문제이다.
BFS, 다익스트라를 이용하여 풀 수 있다.
최소힙을 이용하여 (거리, 다음 마을)를 원소로 담아 목적지까지 가는 경우를 찾았다.
최소힙을 이용한 이유는 거리가 최소가 되는 선에서 목적지까지 도달하는 것을 체크하기 위함이었다.
만약 목적지에 도달한다면 while문을 바로 탈출한다.
- 최소힙을 사용하기 때문에 최소 거리가 보장된다.
이미 계산된 거리가 더 짧다면 더이상 가지 않고 다음 q의 원소를 탐색한다.
그게 아니라면, 다음 마을들을 탐색하여 cost에 임시 거리를 저장하고, 현재 거리보다 짧을 때 update하여 준다. + 최소힙에 다음 원소로 집어 넣는다.
while문을 마치고 나오면, 시작점에 있는 거리와 result(최종적 답안)와의 비교를 통해 더 작은 값을 result에 집어 넣는다.
- 시작점에 있는 거리를 하는 이유는 사이클을 이루려면 시작점으로 되돌아와야 하기 때문이다. (만약 시작점으로 돌아오지 않는다면 int(1e9)의 값을 가질 것이다.

최적화

matrix를 구성할 때 리스트 속 리스트로 구현하면 시간초과가 나오게 된다.
matrix를 구성할 때 리스트 속 딕셔너리로 구현하면 제 시간안에 통과할 수 있다.
그 이유는 dictonary 자료구조에 원소를 더하는 add가 리스트의 append보다 시간이 더 덜 걸리기 때문이다. (참고 : stackoverflow의 관련 질문)
for문을 통해 items()로 탐색하는 것이나 for문을 통해 그냥 리스트를 탐색하는 것은 그렇게 시간차이가 나지 않았다. (개인적으로 실험해 본 결과 오히려 리스트 탐색이 더 빠른 시간이 걸렸다.)
이 문제를 통해 python 자료구조에 대한 이해가 조금은 늘었다.

python code

# 백준 1956번 운동
# 사이클 찾기(최소비용)
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline

v, e = map(int, input().split())
matrix = [{} for _ in range(v)]
# matrix = [[] for _ in range(v)]

for i in range(e):
    a, b, c = map(int, input().split())
    # dictionary add key가 list append 보다 시간이 덜 걸리는 듯 
    matrix[a-1][b-1] = c      
    # matrix[a-1].append((b-1, c))

result = int(1e9)
for start in range(v):
    distance = [int(1e9)]*v
    q = []
    for next, dist in matrix[start].items():
    # for next, dist in matrix[start]:
        distance[next] = dist
        heappush(q, (distance[next], next))
    while q:
        dist, now = heappop(q) 
        if now == start:    # 목적지 도달시 while 탈출
            break

        if distance[now] < dist: # 이미 거리 계산이 되어있는 것이 짧으면 더이상 계산할 필요 없음
            continue

        for next, next_dist in matrix[now].items():
        # for next, next_dist in matrix[now]:
            cost = dist + next_dist
            if cost < distance[next]:
                distance[next] = cost
                heappush(q, (cost, next))
    result = min(distance[start], result)
        
print(result if result != int(1e9) else -1)