도시 분할 계획 ( 1647 번 )

1647번: 도시 분할 계획

 

🧠 알고리즘

크루스칼 알고리즘 (유니온 파인드)

 

🧾 코드

import sys

def _pt_ck(num):
    if pt_list[num - 1] != num:
        pt_list[num - 1] = _pt_ck(pt_list[num - 1])
    return pt_list[num - 1]

def _union(x, y):
    x, y = _pt_ck(x), _pt_ck(y)
    if x > y:
        pt_list[x - 1] = y
    else:
        pt_list[y - 1] = x

def _main(road):
    answer, max_road = 0, 0
    for a, b, c in road:
        if _pt_ck(a) != _pt_ck(b): # 최상위 부모가 다름 ( 즉, 사이클 없음 )
            answer += c
            max_road = max(max_road, c)
            _union(a, b)

    return answer, max_road
                        

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

result_road, big_road = _main(road)
print(result_road - big_road)

 

⏱️ 시간 복잡도

# 정렬 알고리즘 : 선형 로그 시간 복잡도
road = sorted(road, key=lambda x:x[-1]) 

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

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