[알고리즘] 백준 1197(파이썬)

이 문제를 처음에는 DFS, BFS와 같은 방식으로 접근하려고 했다. 하지만 양 끝 정점을 찾기가 힘들어 포기하게 되었고, 최소 값을 구하는 거기 때문에 그리디 알고리즘으로 접근해야 하는 것을 알게 되었다. 조사해보니 최소 스패닝 트리를 푸는 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 있었다. 이 두 알고리즘의 차이는 다음에 기회가 되면 포스팅해야겠다. 여하튼 크루스칼 알고리즘으로 문제를 풀려고 했는데 이 때 쓰이는 알고리즘으로 유니온-파인드 알고리즘이 있다. 이는 두 집합을 합치고 최고 조상을 확인시켜 주는 알고리즘이다.

import sys
node, edge = map(int, sys.stdin.readline().split())

weight = []

for i in range(edge):
    a, b, w = map(int, sys.stdin.readline().split())

    weight.append([w, a, b])

weight.sort()

check = [i for i in range(node+1)]
# print(check)
def find(li, a):
    if li[a] != a:
        li[a] = find(li, li[a])

    return li[a]

def union(li, a, b):
    a = find(li, a)
    b = find(li, b)

    if a > b:
        li[a] = b
    else:
        li[b] = a

ans = 0
# print(weight)

for tar, n1, n2 in weight:
    # print(check,'before find', tar)
    if find(check, n1) != find(check, n2):
        # print(check,'after find')
        ans += tar
        if check[n1] < check[n2]:           # 중요 !!! 최고 조상의 조상을 바꿔야한다!
            check[check[n2]]= check[n1]
        else:
            check[check[n1]] = check[n2]

        # union(check, n1, n2)


    # print(check,'end',n1,n2)
    # print(check,tar)

# print(check)
print(ans)

처음에 파인드를 하고나서 유니온을 할 때 두 비교한 정점의 값을 비교하여 양 정점의 값을 바꿔줬는데 이러면 나중에 양 접점의 최고 조상끼리 만나면 사이클이 되어 값을 추가하면 안되는데 최고 조상의 값은 바꿔지지 않았으므로 서로 find시에 다른 값이 나오게 된다. 따라서 두 정점을 비교하고 최고 조상의 조상을 바꿔줘야한다.(매우 중요!!)