[BOJ] 1647. 도시 분할 계획 (🥇, MST)

🔗

풀이

도시를 둘로 분리하고 분리된 마을들끼리는 최소한의 경로로 연결되어 있어야 한다. 길의 유지비가 최소가 되도록 해야 한다고 한다. 그렇다면 둘로 나누기 전에 모든 마을을 최소한의 길로 연결하고 가장 큰 유지비를 가지는 길을 끊으면 되지 않을까? 그럼 둘로 나뉘면서 최소한의 유지비를 가질 수 있을 것이다.

1. 프림 알고리즘 풀이

# 도시 분할 계획
import sys
import heapq
input = sys.stdin.readline
from collections import defaultdict

n, m = map(int, input().split())
graph = defaultdict(list)
mst = [False]*(n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

def prim():
    cost = []
    pq = [(0, 1)]
    
    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if mst[cur_node]:
            continue
        
        mst[cur_node] = True
        cost.append(cur_cost)
        if len(cost) == n:
            return sum(cost) - max(cost)
        
        for next_node, next_cost in graph[cur_node]:
            if not mst[next_node]:
                heapq.heappush(pq, (next_cost, next_node))


print(prim())

2. 크루스칼 풀이

# 도시 분할 계획
import sys
input = sys.stdin.readline

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

def union(a, b):
    par_a = find(a)
    par_b = find(b)

    if par_a < par_b:
        parent[par_b] = par_a
    else:
        parent[par_a] = par_b

n, m = map(int, input().split())
graph = []
parent = [i for i in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph.append((a-1, b-1, c))

graph.sort(key=lambda x: x[-1])
cost = 0
count = 0
for a, b, c in graph:
    if count == n-2:
        break

    if find(a) != find(b):
        union(a, b)
        cost += c
        count += 1

print(cost)