[🥇4 / 백준 1197 / 파이썬] 최소 스패닝 트리

 

1197번: 최소 스패닝 트리

 

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

예제 입력  3 3 1 2 1 2 3 2 1 3 3

예제 출력  3

 

풀이

 

우선, 이 문제의 그래프는 무방향 그래프임을 밝힌다.

방향 그래프인줄 알고 시간을 허비했는데, 여러분은 그러지 않길 바란다.

 

최소 스패닝 트리, 즉 최소 신장 트리(Minimum Spannig Tree)는 최소한의 비용으로 모든 간선을 연결한 트리를 의미한다.

 

최소 신장 트리를 만드는 알고리즘으로 프림 알고리즘, 그리고 크루스칼 알고리즘이 있다.

크루스칼 알고리즘은 유니온 파인드를 알아야 구현이 가능하므로 이번에는 패스하도록 한다.

 

프림 알고리즘은 heap 자료구조를 이용한다는 점에서 다익스트라와 비슷하다.

단, heap에 넣는 가중치가 다익스트라는 시작 정점에서 현재까지 이어져 온 실제 길이라면,

프림은 그냥 실제 간선 자체의 가중치를 넣는다.

 

visit 배열을 만들고 방문하지 않은 정점들을 탐색하며 연결된 간선들 중 방문하지 않은 정점과 연결된 간선을 heap에 넣는다.

그리고 heap 자료구조이니, 가장 작은 가중치의 간선들을 순서대로 뽑게 된다.

여기서 방문하지 않은 정점들만 사용하여 또 다시 다른 정점들을 탐색한다.

 

heap이 비게 되거나 위와 같은 탐색이 총 v-1 번 진행되었다면, 반복을 종료한다.

최소 스패닝 트리의 간선은 무조건 v-1개가 만들어지게 된다.

 

출처 : 위키피디아

 

시작 정점은 정해져 있지 않으므로, 아무 정점이나 골라서 넣으면 된다.

필자는 1번 노드를 넣었다.

 

import sys,heapq
input = sys.stdin.readline

v,e = map(int,input().split())
cnt,hq = 0,[]
visit = [0]*(v+1)

# 그래프 구성
link = [[] for _ in range(v+1)]
for _ in range(e):
    a,b,c = map(int,input().split())
    link[a].append((c,b))
    link[b].append((c,a))

# 임의의 정점을 힙에 넣음
visit[1] = 1
for i in link[1]:
    heapq.heappush(hq,i)

result = 0
while hq:
    # 간선이 총 v-1개 이루어졌다면 종료
    if cnt == v-1:
        break
        
    w,node = heapq.heappop(hq)
    if visit[node]:
        continue
    
    cnt+=1
    result+=w
    visit[node] = 1
    for i in link[node]:
        tw,tnode = i
        if visit[tnode]:
            continue
        heapq.heappush(hq,i)
print(result)