최소 스패닝 트리 ( 1197 번 )

1197번: 최소 스패닝 트리

 

🧠 알고리즘

- Kruskal 알고리즘 사용
- 간선을 가중치 기준으로 정렬한 뒤, 사이클이 생기지 않도록 간선을 하나씩 선택
- Union-Find (Disjoint Set) 자료구조 활용

 

🧾 코드

import sys

def _find(idx):
    if pt_list[idx - 1] == idx:
        return idx
    else:
        pt_list[idx - 1] = _find(pt_list[idx - 1])
        return pt_list[idx - 1]


def _union(x, y):
    pt_list[x - 1], pt_list[y - 1] = _find(x), _find(y)

    if pt_list[x - 1] < pt_list[y - 1]:
        pt_list[y - 1] = pt_list[x - 1]
    else:
        pt_list[x - 1] = pt_list[y - 1]
        

def _main(n_list):
    answer = 0
    for a, b, c in n_list:
        if _find(a) != _find(b):
            answer += c
            _union(a, b)

    return answer
            

v, e = map(int, sys.stdin.readline().rstrip().split())
n_list = sorted([tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(e)], key=lambda x:x[-1])
pt_list = [i for i in range(1, v + 1)]

print(_main(n_list))

 

⏱️ 시간 복잡도

# 정렬 알고리즘 : 선형 로그 시간 복잡도
sorted([tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(e)], key=lambda x:x[-1])

# _main() : 최소 스패닝 트리, 경로 압축 : 선형 시간 복잡도

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )