1197 - 최소 스패닝 트리

 

---

 

문제

https://www.acmicpc.net/status?user_id=whipbaek&problem_id=1197&from_mine=1 

채점 현황

 

풀이

제목 그대로 최소스패닝트리(MST)를 만드는 문제다.

MST를 만드는 방법으로는 크루스칼과 프림 알고리즘 두개가 있는데 나는 크루스칼을 활용하여 풀었다.

 

크루스칼은 edge들의 비용순으로 오름차순 한 후에, 하나씩 연결해보는 알고리즘이다.

연결하다가 사이클이 발견되면 그 edge는 뛰어넘고 다음 edge를 확인해보는 식으로 반복된다.

 

이 때 사이클을 감지하기 위하여 union find 알고리즘을 활용한다. 연결하려는 두 노드의 루트노드가 같다면 사이클이 존재한다는 것이다. 사이클이 발생하지 않을경우에만 비용값을 더해주고 최종값을 출력해주면 해결할 수 있다.

 

코드

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    # 작은 숫자가 루트 노드가 되도록 설정
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())

edges = []

parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i

for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append([cost, a, b])

# edge들을 cost 오름차순 정렬
edges.sort()
answer = 0
for edge in edges:
    # 부모가 다르다면 (사이클이 없다면)
    if find_parent(parent, edge[1]) != find_parent(parent, edge[2]):
        union_parent(parent, edge[1], edge[2])
        answer += edge[0]

print(answer)

 

후기

 

union find로직만 잘 기억하고 있자.