[파이썬] 백준 1197 : 최소 스패닝 트리 (골드4)

[파이썬] 백준 1197 : 최소 스패닝 트리 (골드4)

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

---

풀이

방향성 생각

• 유니온 파인드로 구현.
• 시간 줄이고 싶으면 모든 노드가 연결되면 탈출하는 방식으로 풀이.
• 루프 방지를 위해서 항상 번호가 작은 노드를 루트로 한다.
• 이 문제의 경우에는 그냥 넘어가지만, 모든 노드가 어떻게 연결되었는지 확인을 해야하는 경우에는 각 노드마다 find(node)로 경로압축을 꼭 해주자.

---

전체코드

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

V,E = map(int,input().split())
G = [list(map(int,input().split())) for _ in range(E)]
G.sort(key=lambda x:x[2])

P = [i for i in range(V+1)]

def find(a):
    if P[a] != a:
        P[a] = find(P[a])
    return P[a]

def union(pa,pb):
    P[max(pa,pb)] = min(pa,pb)

answer = 0
for (a,b,cost) in G:
    pa,pb = find(a),find(b)
    if pa != pb:
        union(pa,pb)
        answer += cost

print(answer)

코멘트

• 아니 너무 오랜만이라 재귀 깊이 제한때매 틀리는거도 몰랐다... 로직에 문제있는줄
• 덕분에 오랜만에 내 블로그 뒤져가면서 경로압축이랑 이것저것 다시 공부..