[Python] 백준 1647 도시 분할 계획

문제

입출력

풀이

해당 문제는 크루스칼 알고리즘을 통해 최소 비용 신장 트리를 구하는 것입니다.
크루스칼 알고리즘이란 가장 적은 비용으로 모든 노드를 연결하는 알고리즘입니다.
추가적으로 알고리즘 이해가 필요하신 분은 나동빈님 크루스칼 알고리즘
보고 오시는 걸 추천드립니다!!

크루스칼 알고리즘(Kruskal Algorithm)의 핵심은 Union-Find 알고리즘입니다!

쉽게 설명하면, 자기자신을 root 노드로 초기화하고

가중치가 작은 노드부터 각각 차례대로(정렬), 하나의 집합에 추가하며 집합에 추가된 노드는 집합 내 root 노드를 부모노드로 갱신합니다.

즉, 아직 집합에 추가되지 않은 노드의 부모노드가, 이미 집합의 root 노드와 동일하다면, 사이클이 존재한다고 판단합니다

코드

import sys
input=sys.stdin.readline
def find(x):
    if parent[x]!=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
        
n,m=map(int, input().split())
graph=[]
parent = list(range(n + 1))
for i in range(m):
    a,b,c=map(int,input().split())
    graph.append((a,b,c))
graph.sort(key=lambda x:x[2])
last=0
answer=0
for a,b,c in graph:
    if find(a)!=find(b):
        union(a,b)
        answer+=c
        last=c
print(answer-last)

참고

https://www.youtube.com/watch?v=LQ3JHknGy8c
https://blog.naver.com/ndb796/221230967614
https://velog.io/@sihoon_cho/BOJ%EB%B0%B1%EC%A4%80-1647%EB%B2%88-%EB%8F%84%EC%8B%9C-%EB%B6%84%ED%95%A0-%EA%B3%84%ED%9A%8D-Python%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%95%B4%EC%84%A4%ED%92%80%EC%9D%B4