[BOJ] 백준 14621번 문제 풀이 (Python)

1. 문제 풀이

크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 구하였습니다.

출력이 -1이 되는 경우는 최소 스패닝 트리가 이루어지지 않았을 경우이기 때문에 count 변수를 이용하여 도로가 N-1개 미만으로 연결된 경우 -1로 출력했습니다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

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

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

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())
school = ['-1']+ list(input().split())
parent = [ i for i in range(n+1)]
edges = [ tuple(map(int, input().split())) for _ in range(m)]
edges.sort(key=lambda x: x[2])
result, cnt = 0,0
for a, b, c in edges:
    if school[a] == school[b]: continue
    if find_parent(parent, a) != find_parent(parent, b):
        union(parent, a, b)
        result += c
        cnt += 1
if cnt == n-1:
    print(result)
else:
    print(-1)