064 최소 스패닝 트리

첫번째 코드

 

최소 신장 트리 알고리즘을 이용한 문제이다.

코드는 책을 참고했다.

 

유니온 파인드와 최단 거리가 섞인 문제로 유니온 파인드에 대한 명확한 이해가 필요하다.

부모노드와 최단 거리를 함께 생각하는 문제로

개념을 이해하면 원리는 이해가 되지만

코드 작성하려고 손을 올리면 멈추게 되는 문제이다.

 

다음에 다시 풀어보아야 하는 문제이다.

혼자 모두 이해하고 적을 수 있다면 최소 신장 트리와 유니온 파인드를 모두 이해했다는 것이 아닐까

 

import sys
input = sys.stdin.readline
from queue import PriorityQueue

n, m = map(int, input().split())
queue = PriorityQueue()
parent = [0] * (n+1)

for i in range(n+1):
    parent[i] = i

for _ in range(m):
    s, e, w = map(int, input().split())
    queue.put((w, s, e))

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    
    if a != b:
        parent[b] = a

useEdge = 0
result = 0

while useEdge < n-1:
    w, s, e = queue.get()
    if find(s) != find(e):
        union(s, e)
        result += w
        useEdge += 1

print(result)

 

통과

 

개념을 바로바로 정리하고 이해하여 푸는게 훨씬 코드 이해에 편한 것 같다!

다음에 또 풀어보기!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1197.%E2%80%85%EC%B5%9C%EC%86%8C%E2%80%85%EC%8A%A4%ED%8C%A8%EB%8B%9D%E2%80%85%ED%8A%B8%EB%A6%AC

programmers/백준/Gold/1197. 최소 스패닝 트리 at main · ornni/programmers