백준 1197 최소 스패닝 트리 문제풀이

문제 

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

1197번: 최소 스패닝 트리

 

 

 

문제 접근 방식

주어진 그래프의 스패닝 트리 중 최소 스패닝 트리를 구하는 문제이다. 이를 해결하기 위해, 최소 길이의 간선을 우선적으로 선택하는 크루스칼 알고리즘을 사용하였다. 

 

크루스칼 알고리즘에서는 최소 간선을 계속해서 찾아야하기 때문에 우선순위 큐를 사용하여 최소 간선만을 찾도록 하였다. 만약 큐에서 pop 한 두 노드가 이미 최소 스패닝 트리에 존재할 경우 pass 한다.

 

시간 복잡도

우선 순위 큐를 사용하기 때문에 O(ElogE) 이 걸리며, 각 find와 union 함수의 경우 상수시간이 걸리기 때문에 전체적인 시간복잡도는 O(ElogE) 이다. E의 최댓값이 1e5이므로 제한시간내에 동작한다.

 

코드

import sys
import heapq

input=sys.stdin.readline
class UnionFind:
    def __init__(self,v):
        self.parents=[i for i in range(v+1)]
        self.heights=[1 for _ in range(v+1)]

    def find_parents(self,node):
        if self.parents[node]==node:
            return node

        self.parents[node]=self.find_parents(self.parents[node])
        return self.parents[node]

    def union(self,u,v):
        u=self.find_parents(u)
        v=self.find_parents(v)

        if u==v:
            return

        if self.heights[u]<self.heights[v]:
            u,v=v,u

        self.parents[v]=u
        if self.heights[u]==self.heights[v]:
            self.heights[u]+=1




if __name__=='__main__':
    v,e=map(int,input().split())

    pq=[]

    # 우선순위 큐 pq에 (가중치, 노드1,노드2) 를 넣어준다
    for _ in range(e):
        a,b,c=map(int,input().split())

        heapq.heappush(pq,(c,a,b))

    union_find=UnionFind(v)
    count=0
    answer=0
    # 작은 가중치를 갖는 간선부터 pop
    while pq:
        w,a,b=heapq.heappop(pq)

        if union_find.find_parents(a)==union_find.find_parents(b):
            continue

        # 서로 다른 집합이라면 두 집합을 합치고, 최소 경로 길이에 추가한다.
        union_find.union(a,b)
        answer+=w
        count+=1

        if count==v-1:
            break

    print(answer)

 

 

회고

최소 스패닝 트리(MST) 핵심

1. 우선 순위 큐를 사용하여 최소 길이 간선을 탐색
2. 유니온 파인드 자료구조로 이전에 선택한 노드인지 판단
3. 간선 선택 개수를 추적하여 v-1개라면 우선순위큐 순회 종료