[Python/파이썬] 백준 14284번 간선 이어가기 2

14284번: 간선 이어가기 2

 

문제

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

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

입력

첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤5000,1≤m≤100,000)

다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다. (1≤a,b≤n,1≤c≤100,a≠b)

다음 줄에는 두 정점 s,t가 주어진다. (1≤s,t≤n,s≠t)

모든 간선을 연결하면 그래프는 연결 그래프가 됨이 보장된다.

출력

s와 t가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오.

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
edges = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    edges[a].append((b, c))
    edges[b].append((a, c))

s, t = map(int, input().split())

# dijkstra
dist = [int(1e9)] * (n+1)
dist[s] = 0
q = [(0, s)]
while q:
    d, now = heappop(q)
    for nx, nd in edges[now]:
        if d+nd < dist[nx]:
            dist[nx] = d+nd
            heappush(q, (d+nd, nx))
print(dist[t])

결국은 s부터 t까지의 최단경로를 구하는 문제이다. 그렇기 때문에 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘인 다익스트라를 사용했다.

• s부터 다른 모든 정점들까지의 거리를 저장할 배열 dist를 만들고 시작점인 s의 dist[s] 값은 0으로 초기화해준다.
• 우선순위 큐 q에 거리와 시작점 (0, s)를 넣어준다.
• q가 빌 때까지 아래의 과정을 반복한다.
  • q에서 pop한 정점 now에 대해 인접한 정점 중 now를 거쳐서 그 정점(nx)으로 갈 때 더 최단거리가 되는 정점이 있다면 dist[nx] 값을 s부터 now까지의 거리와 now부터 nx까지 거리의 합인 d+nd로 갱신해주고, q에 (d+nd, nx)를 넣어준다.