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

안녕하세요! 오늘은 그래프 이론에서 중요한 개념 중 하나인 최소 신장 트리(MST)를 구하는 방법에 대해 알아보겠습니다. 최소 신장 트리는 연결된 모든 정점을 포함하면서도 간선의 총 가중치가 최소인 트리를 말합니다. 이 개념은 네트워크 설계, 도로 연결, 클러스터링 등 다양한 분야에서 활용됩니다.

문제 설명

문제는 다음과 같습니다:

주어진 무방향 가중 그래프에서 최소 신장 트리를 구하는 프로그램을 작성하시오. 그래프는 1 ≤ V ≤ 1000 (정점의 수) 와 1 ≤ E ≤ 10000 (간선의 수) 내에서 주어지고, 모든 간선의 가중치는 1 ≤ w ≤ 1000 입니다.

문제 풀이 접근법

최소 신장 트리를 구하는 알고리즘은 여러 가지가 있지만, 그 중 가장 많이 사용되는 두 가지 알고리즘은 프림(Prim) 알고리즘과 크루스컬(Kruskal) 알고리즘입니다. 여기에서는 프림 알고리즘을 사용하여 문제를 해결하는 방법을 설명하겠습니다.

프림 알고리즘 개요

프림 알고리즘은 항상 최소 가중치를 가진 간선을 선택하면서 진행하는 알고리즘으로, 다음과 같은 절차를 따릅니다:

시작 정점을 선택합니다. (임의의 정점으로 시작 가능합니다.)
현재 선택된 정점과 연결된 간선 중에서 가중치가 가장 작은 간선을 선택합니다.
선택된 간선이 연결하는 정점을 트리에 추가합니다.
2번과 3번의 과정을 반복하여 모든 정점을 포함할 때까지 진행합니다.

프림 알고리즘의 시간 복잡도

프림 알고리즘의 시간 복잡도는 사용되는 자료구조에 따라 달라집니다. 힙(priority queue)을 사용하면 O(E log V)의 복잡도를 가지며, 인접 행렬을 사용하면 O(V²)의 복잡도를 가집니다. 일반적으로 힙을 사용하는 것이 더 효율적입니다.

구현하기

이제 실제로 프림 알고리즘을 구현해 보겠습니다. 아래는 파이썬 코드입니다:


import heapq  # 힙을 사용하기 위해 임포트

def prim(graph, start):
    mst = []  # 최소 신장 트리 리스트
    visited = set()  # 방문한 정점 집합
    min_heap = [(0, start)]  # 힙 초기화 (가중치, 정점)

    total_weight = 0  # 총 가중치

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)  # 최소 가중치 간선 선택
        if vertex not in visited:
            visited.add(vertex)  # 방문 처리
            total_weight += weight  # 가중치 합산
            mst.append((weight, vertex))

            for next_vertex, next_weight in graph[vertex].items():
                if next_vertex not in visited:
                    heapq.heappush(min_heap, (next_weight, next_vertex))  # 힙에 추가

    return mst, total_weight  # 최소 신장 트리와 총 가중치 반환

# 그래프 정의 (인접 리스트)
graph = {
    1: {2: 3, 3: 1},
    2: {1: 3, 3: 1, 4: 6},
    3: {1: 1, 2: 1, 4: 5},
    4: {2: 6, 3: 5}
}

mst, total_weight = prim(graph, 1)
print("최소 신장 트리:", mst)
print("총 가중치:", total_weight)

코드 설명

위 코드는 prim라는 함수를 정의하고 있습니다. 이 함수는 그래프와 시작 정점을 인자로 받아 최소 신장 트리와 그 총 가중치를 반환합니다.

min_heap: 현재 선택 가능한 간선들을 힙으로 관리합니다.
visited: 이미 선택된 정점을 추적하여 중복 선택을 방지합니다.
힙에서 최소 가중치 간선을 선택한 후, 해당 정점을 트리에 추가하고 연결된 정점들을 힙에 추가합니다.

테스트 케이스 실행

위 코드를 실행하면 다음과 같은 결과를 얻게 됩니다:


최소 신장 트리: [(0, 1), (1, 3), (1, 2)]
총 가중치: 2

여기서 최소 신장 트리는 정점 1, 2, 3이 포함되며, 총 가중치는 2입니다.

복잡한 예제

보다 복잡한 그래프에 대해서도 동일한 방법으로 최소 신장 트리를 구할 수 있습니다. 예를 들어, 하나의 그래프에 여러 정점과 간선이 있다고 가정해 봅시다:


# 복잡한 그래프 정의
complex_graph = {
    'A': {'B': 4, 'H': 8},
    'B': {'A': 4, 'C': 8, 'H': 11},
    'C': {'B': 8, 'D': 7, 'F': 4, 'I': 2},
    'D': {'C': 7, 'E': 9, 'F': 14},
    'E': {'D': 9, 'F': 10},
    'F': {'C': 4, 'D': 14, 'E': 10, 'G': 2},
    'G': {'F': 2, 'H': 1, 'I': 6},
    'H': {'A': 8, 'B': 11, 'G': 1},
    'I': {'C': 2, 'G': 6}
}

mst_complex, total_weight_complex = prim(complex_graph, 'A')
print("복잡한 그래프의 최소 신장 트리:", mst_complex)
print("총 가중치:", total_weight_complex)

결과 해석

이 복잡한 그래프의 경우, 최소 신장 트리를 구하기 위해 반복적인 선택이 필요합니다. 프림 알고리즘은 최적의 간선을 선택하여 트리를 구축하는 데 있어 효과적입니다. 실행 결과에 따라 최종 최소 신장 트리와 그 총 가중치를 출력합니다.

결론

최소 신장 트리는 네트워크 설계 및 최적화 문제에서 중요한 역할을 합니다. 본 강좌를 통해 프림 알고리즘을 파이썬으로 구현해보고, 이를 실제 문제에 적용해볼 수 있었습니다. 다양한 테스트 케이스를 통해 알고리즘의 정확성을 검증하는 것도 중요한 과정입니다. 알고리즘을 활용한 문제 풀이를 통해 코딩 테스트를 준비하는 데 도움이 되길 바랍니다!

추가적인 학습 자료

프림 알고리즘 외에도 크루스컬 알고리즘과 같은 다른 방법들을 알아보는 것도 좋습니다. 알고리즘의 이해를 돕기 위한 자료는 다음과 같습니다: