백준 1647:도시 분할 계획(python) 크루스칼 알고리즘

MST의 전형적인 문제이다.

크루스칼 알고리즘의 구동 과정을 설명해보겠다.

1. 간선을 가중치 기준으로 오름차순 정렬한다.

2. 간선을 정렬한 순으로 하나하나 추가해준다.

3. 상호 배타적 집합 자료구조(Union-Find)를 사용하여 사이클을 판별한다.

 

크루스칼의 구현은 위와 같이 간단하다.

 

그리고 도시 분할 계획 문제에서는 도시를 분할하여야 하므로, 가장 큰 비용의 마지막 간선을 제거해준다.

 

코드는 다음과 같다.

import sys
input = sys.stdin.readline
print = sys.stdout.write
n, m = map(int, input().rstrip().split())
adj = []# tuple을 이용해 (가중치, 연결된 정점1, 연결된 정점2) 저장
def min(a, b):
    if a < b: return a
    return b
def max(a,b):
    if b < a: return a
    return b
momnode = [i for i in range(n+1)]
def find(x):
    if momnode[x] != x:
        momnode[x] = find(momnode[x])
    return momnode[x]
def union(x, y):
    momnode[find(y)] = find(x)
for i in range(m):
    a, b, w = map(int, input().rstrip().split())
    adj.append((w,a,b))
adj.sort()
ans = 0
m = 0
for p in adj:
    a = p[1]
    b = p[2]
    w = p[0]
    if find(a) != find(b):
        union(min(a,b), max(a,b))
        ans += w
        m = w
print(str(ans-m))

코딩 새싹 무끝을 귀욤귀욤 해주세여 ><