[Python/Baekjoon] B1647. 도시 분할 계획

💬 문제

문제 난이도: 골드 4

문제 링크: https://www.acmicpc.net/problem/1647

문제 설명

한 마을에 N개의 집들이 있고, 그 집들을 연결하는 M개의 길이 있다. 각 길마다 길을 유지하는 유지비용이 있다.
이 마을을 두 마을로 분리하고 싶다. 이 때 각 마을에 있는 집들은 서로 연결되어 있어야 한다. 모든 길을 사용할 필요는 없다.
마을을 둘로 나누고 위의 조건을 만족할 때 드는 길의 유지비용의 최솟값을 출력하라.

❗️접근 방법

MST

최소 스패닝 트리는 N개의 노드로 이루어진 연결 그래프에서 모든 노드를 연결하면서 사이클을 만들지 않는 스패닝 트리 중 간선의 가중치 합이 최소가 되는 트리이다.
가중치가 최소가 되고 사이클이 없어야 하므로 N개의 노드를 연결할 때 N-1개의 간선으로 연결되어 있다.
이 문제에서 모든 집을 연결하는 MST를 만든 후, 가장 가중치가 큰 간선 하나를 빼면 마을이 둘로 분리되면서 가중치의 합이 최소가 된다.

Kruskal

Kruskal 알고리즘은 간선 중심으로 MST를 찾는 알고리즘이다.
이 문제에서 MST를 만들고 MST에서 가장 가중치가 큰 간선을 하나 제거하므로써 마을을 둘로 분리할 수 있다.
따라서 기존 Kruskal 알고리즘이 트리에 포함된 간선의 개수가 N-1일 때 while문을 종료했다면,
이 문제는 N-2일 때 while문을 종료하면 된다.

코드(Kruskal)

import sys
input = sys.stdin.readline

N, M = map(int, input().split(' '))
parents = [i for i in range(N+1)]
edges = []
for _ in range(M):
    edges.append(list(map(int, input().split(' '))))
edges.sort(key=lambda x: x[2])


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

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

def kruskal():
    total_cost = 0
    connected_edges = 0
    for [n1, n2, w] in edges:
        if connected_edges == N-2:
            break
        if find(n1) != find(n2):
            union(n1, n2)
            total_cost += w
            connected_edges += 1
    return total_cost

print(kruskal())