(Python/파이썬) - 백준(BOJ) 14284번 : 간선 이어가기 2

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

14284번: 간선 이어가기 2

---

• 문제 : 

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.

 

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

 

 

 

---

• 풀이 :

다익스트라의 기본 문제였습니다.

 

다익스트라 알고리즘의 흐름은 다음과 같습니다.

 

 

1. distance를 저장하는 배열을 생성 이 때 배열의 값은 시작점에서 다른 모든 노드로 가는 최솟값으로 갱신 예정이므로 

엄청나게 큰 수를 초깃값으로 지정해야 함.

 

2. heap 자료구조를 사용하여 코스트가 낮은 경로부터 탐색하며 가중치를 더 낮은 값으로 갱신해줌. 이 때, 시작노드의 가중치는 0임

 

3. 모든 경로를 탐색하면 distance의 i번째 인덱스에 가중치 최솟값이 들어있음.

 

 

말로 설명하려니 좀 어렵네요 개념을 쉽게 잘 정리한 사람들이 많으니 그걸 참고하는게 더 나아보입니다... 

 

 

 

 

 

---

• 소스코드 : 

import heapq as hq
import sys
input = sys.stdin.readline

def dijkstra(S,T):
    distance = [float('inf') for _ in range(N+1)]
    distance[S] = 0
    heap = [(0,S)]
    while heap:
        curr_cost, curr_node = hq.heappop(heap)
        if distance[curr_node] < curr_cost:
            continue
        for next_node, next_cost in graph[curr_node]:
            total_cost = next_cost + curr_cost
            if total_cost < distance[next_node]:
                distance[next_node] = total_cost
                hq.heappush(heap,(total_cost, next_node))
    return distance[T]

N,M = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])
S, T = map(int,input().split())
print(dijkstra(S, T))