14284. [Python]간선 이어가기 2

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 다익스트라 알고리즘

 

3. 파이썬 코드

 

import sys
import heapq

input = sys.stdin.readline
# 다익스트라 알고리즘
def dijkstra(start):
    # q 초기화
    q = []
    # heapq 로 q 리스트 생성
    heapq.heappush(q,(0,start))
    # distance로 초기 시작점 0 으로 초기화
    distance[start] = 0
    # q 값이 존재할 경우 반복문 진행
    while q:
        # 거리, 현재 값으로 값을 뽑아냄
        dist, now = heapq.heappop(q)
        # 저장된 거리가 현재 값보다 작은 경우 다음 반복문
        if distance[now] < dist:
            continue
        # 연결된 (가중치, 노드값) 반복
        for i in graph[now]:
            # 비용에 현재 값 + 가중치 더해줌
            cost = dist + i[0]
            # 비용이 거리보다 작은 경우
            if cost < distance[i[1]]:
                # 거리 값 갱신
                distance[i[1]] = cost
                # 비용과 노드 추가
                heapq.heappush(q,(cost,i[1]))

N, M = map(int,input().split())

distance = [10 ** 9] *(N+1)
graph = [[]for _ in range(N+1)]

for _ in range(M):
    S,E,W = map(int,input().split())
    graph[S].append((W,E))
    graph[E].append((W,S))

S,T = map(int,input().split())

dijkstra(S)
print(distance[T])

 

4. 문제를 풀고난 후 생각

 

• 문제 자체가 조금 어렵게 작성 돼있어서 이해하는 부분에서 어려움을 겪었다.
• 단순히 해석하면 다익스트라 알고리즘을 돌리기만 하면 최소값이 나오기 때문에 다익스트라 알고리즘을 사용할 수 있는지를 묻는 문제였다.
• 마지막 문장인 ' s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.' 부분에서 문장을 이해를 잘 하면 됐던 문제다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 다익스트라 알고리즘