백준 1197번: 최소 스패닝 트리 (Minimum Spanning Tree)

문제링크:1197번: 최소 스패닝 트리 (acmicpc.net)

1197번: 최소 스패닝 트리

 

최소 스패닝 트리란 트리의 모든 정점을 연결하는 부분 그래프들 중 가중치 합이 최소인 부분 그래프이다. 모든 정점을 연결해야 하기 때문에 당연히 모든 정점을 연결 할 수 있는 그래프 입력이 주어진다. 문제를 푸는 방법에는 크루스칼 알고리즘과 프림 알고리즘이 있는데, 처음에 생각한 방법이 프림 알고리즘에 가까워 프림 알고리즘을 사용해 풀었다. 프림 알고리즘이란 일단 시작 정점를 하나 방문처리한다. 그리고 방문 처리된 정점들의 간선들 중 가장 가중치가 작은 간선을 탐색하는데, 이 간선이 방문되지 않은 정점과 연결된다면 잘 찾은 것이므로 최소 스패닝 트리에 더해주고 방문되지 않은 정점을 방문 처리 해준다. 반면에 탐색한 간선이 이미 방문한 정점과 연결되어 있다면 제거하고 다음으로 가중치가 작은 간선을 탐색한다. 모든 정점이 방문처리 되면, 최소 스패닝 트리가 생기게 된 것이다.

import sys
import heapq

V,E=map(int,sys.stdin.readline().rstrip().split())

graph=[[] for _ in range(V+1)]

for _ in range(E):
    a,b,c=map(int,sys.stdin.readline().rstrip().split())
    graph[a].append([b,c])
    graph[b].append([a,c])

que=[]
visited=[0 for _ in range(V+1)]
visited[1]=1
visits=1
for i in graph[1]:
    dis=i[1]
    node=i[0]
    heapq.heappush(que,[dis,node])

result=0
while que:
    if visits==V:
        break
    disnode=heapq.heappop(que)
    dis=disnode[0]
    node=disnode[1]
    if visited[node]==0:
        visited[node]=1
        visits+=1
        result+=dis
        for i in graph[node]:
            if visited[i[0]]==0:
                heapq.heappush(que,[i[1],i[0]])

print(result)

나는 시작 정점을 1로 잡았지만 최소 스패닝 트리는 모든 정점을 연결하기에 어디로 잡아도 상관 없다. heap자료구조를 이용해 최소 가중치인 간선을 빠르게 찾을 수 있고, 매번 방문한 정점들의 간선을 찾기보다 가장 처음 간선들을 que에 넣고 새로운 정점을 찾을때마다 정점의 간선들을 que에 누적해 추가 해 주어 시간을 줄였다. 간선을 추가하는 과정에서 이미 방문된 정점으로 연결되는 간선은 que에 더해봤자 쓸모 없으니 방문되지 않은 정점으로 연결되는 간선만 추가하였다. 모든 정점이 방문되면 최소 스패닝 트리가 완성되는데, visited 리스트를 탐색하기보다 새로운 정점 탐색시 마다 visits를 1씩 더해주어 visits읙 값이 V면 끝이므로 모든 정점 방문을 빠르게 판단하게 만들었다.