[Python] 백준 1647 - 도시 분할 계획 문제 풀이

Overview

BOJ 1647번 도시 분할 계획 Python 문제 풀이
분류: Minimum Spanning Tree (최소 스패닝 트리), Kruskal Algorithm (크루스칼 알고리즘)

---

문제 페이지

https://www.acmicpc.net/problem/1647

---

풀이 코드

from sys import stdin
from collections import defaultdict
from typing import List


parents = defaultdict(int)


def find(x: int) -> int:
    if parents[x] == 0:
        return x
    parents[x] = find(parents[x])
    return parents[x]


def union(x: int, y: int) -> None:
    x, y = find(x), find(y)
    if x < y:
        parents[y] = x
    else:
        parents[x] = y


def mst(n: int, graph: List[tuple]) -> int:
    cost = 0
    graph.sort()

    for w, a, b in graph:
        a, b = find(a), find(b)
        if a == b:
            continue

        union(a, b)
        cost += w
        n -= 1

        if n == 2:
            break

    return cost


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    graph = []

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

    print(mst(n, graph))


if __name__ == "__main__":
    main()

크루스칼 알고리즘을 이용하여, 두 개의 최소 신장 트리를 만드는 문제이다.
루트 노드(부모 노드)가 2개만 남을 때까지 최소 신장 트리를 만들며, 간선 비용을 더한다.

이 방법 말고도 하나의 최소 신장 트리를 완성한 뒤에, 마지막에 추가된 간선을 제거해도 동일한 결과가 나온다.

이 풀이에서 각 노드의 부모 값을 저장하는 parents는 list 자료형이 아닌 defaultdict 자료형을 이용하였다. 동일한 유형 문제에서 전체 크기를 엄청나게 늘려서 출제하는 경우, list가 아닌 해시나 이진트리를 활용하여 유니언 파인드 구조를 사용해야 하기 때문에 미리 연습해 보았다.