문제
접근
최소 스패닝 트리 문제이다.
그래프에서 최소 비용을 사용하여 트리 구조를 만든다고 생각하면 된다.
그래프 표현은 인접 리스트 방식을 사용했고, 프림 알고리즘을 이용하여 해결했다.
방문 여부를 나타내는 배열하나와 현재까지 방문한 노드들 중 다음 노드와 연결하기 위한 최소 비용을 찾기 위해 우선순위 큐를 사용했다.
n개의 노드를 연결하기 위해서는 최소 n-1개의 간선이 필요하므로, 연결 과정을 n-1번 반복하면 멈추도록 하였다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import heapq
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
adj = [[] for _ in range(n)]
for i in range(m):
a, b, w = map(int, input().split())
adj[a-1].append((w,b-1))
adj[b-1].append((w,a-1))
visited = [0] * n
pq = []
for w, node in adj[0]:
heapq.heappush(pq, (w, node))
visited[0] = 1
cnt = 0
ans = 0
while pq:
w, node = heapq.heappop(pq)
if visited[node]:
continue
visited[node] = 1
ans += w
cnt += 1
if cnt == n-1:
break
for w, nxt in adj[node]:
if visited[nxt] == 0:
heapq.heappush(pq, (w, nxt))
print(ans)