파이썬 코딩테스트 강좌, 최소 신장 트리

1. 최소 신장 트리란?

최소 신장 트리(Minimum Spanning Tree, MST)는 연결 그래프에서 모든 정점을 포함하면서
간선의 가중치의 합이 최소가 되는 부분 그래프입니다. 즉, 최소 신장 트리는 주어진 그래프에서
사이클을 형성하지 않으면서 전체 최소 비용으로 연결되는 트리를 찾는 과정입니다.

2. 문제 설명

다음은 최소 신장 트리 문제입니다:

주어진 n개의 도시와 m개의 도로에 대한 정보가 주어질
때, 모든 도시를 최소한의 비용으로 연결하는 도로의 비용의 최솟값을 구하세요.

입력 형식: 첫 번째 줄에 두 정수 n (도시의 수)와 m (도로의 수)이 주어집니다.
다음 m개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 a, b, c가 주어지며,
이는 도시 a와 도시 b를 연결하는 도로의 비용이 c임을 의미합니다.

3. 접근법

최소 신장 트리 문제를 해결하기 위해서는 일반적으로 두 가지 알고리즘을 많이 사용합니다:

• 프림(Prim) 알고리즘
• 크루스칼(Kruskal) 알고리즘

이번 글에서는 크루스칼 알고리즘을 사용하여 문제를 해결해 보겠습니다.

3.1 크루스칼 알고리즘

크루스칼 알고리즘은 다음과 같은 단계로 진행됩니다:

1. 모든 간선을 가중치(비용)에 따라 오름차순으로 정렬한다.
2. 가장 작은 간선부터 시작해 선택한다. 선택한 간선이 사이클을 형성하지 않는다면 MST에 포함시킨다.
3. 모든 간선을 검사할 때까지 2번 과정을 반복한다.

4. 알고리즘 구현

이제 위의 문제를 해결하기 위한 크루스칼 알고리즘의 파이썬 구현을 시작하겠습니다.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
    

4.1 입력 및 간선 정렬

입력으로 도시의 수와 도로 정보를 받아오고, 간선을 가중치에 따라 정렬합니다.

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    edges = []

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

    edges.sort()  # 가중치 오름차순 정렬
    

4.2 크루스칼 알고리즘 적용

정렬된 간선들을 하나씩 확인하면서 MST를 구성합니다.

    ds = DisjointSet(n)
    mst_cost = 0

    for cost, a, b in edges:
        if ds.find(a) != ds.find(b):  # 사이클 확인
            ds.union(a, b)
            mst_cost += cost

    print(mst_cost)  # 최소 신장 트리 비용 출력
if __name__ == "__main__":
    main()
    

5. 결론

이번 글에서는 최소 신장 트리의 개념과 크루스칼 알고리즘을 통해 문제를 해결하는 방법을
알아보았습니다. 여러분도 주어진 문제를 자신만의 방식으로 분석하고 해결할 수 있는 능력을
키우길 바랍니다.