[백준 BOJ / Python] 1197번 최소 스패닝 트리

문제

그래프가 주어졌을 때 최소 스패닝 트리(최소 신장 트리)를 구하고 그의 가중치를 출력하는 문제이다.

풀이

• 크루스칼 알고리즘을 사용하여 가중치를 계산한다.
  1. 간선(edge)을 가중치가 작은 순으로 정렬한다.
  2. 부모 노드를 자기 자신으로 초기화한다.
  3. 가장 작은 가중치부터 순서대로 노드를 서로 연결한다.
     노드를 서로 연결한다는 것은 두 노드가 같은 루트를 갖게 한다는 의미이다.
     즉 부모 노드가 다를 경우, 아직 서로 연결이 안 된 노드이기에
     union을 통해 부모 노드를 동일하게 만들어 줌으로써 서로 연결하는 것이다.

Python 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

v,e = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(e)] # a,b,c
parent = list(range(v+1))
res = 0

# 간선을 최소 비용 순으로 오름차순 정렬
edges.sort(key = lambda x: x[2])

# Union-Find 알고리즘
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    x = find(x)
    y = find(y)

    if x <= y:
        parent[y] = x
    else:
        parent[x] = y
        
# 크루스칼 알고리즘
for i in range(e):
    x,y,c = edges[i]
    if find(x) != find(y): # 부모 노드가 다름
        union(x,y) # 최소 신장트리에 포함시킴
        res += c

print(res)

 

문제출처

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

 

최소신장트리 크루스칼 알고리즘

[알고리즘 / Python] 최소신장트리 (크루스칼 알고리즘)