파이썬 백준 알고리즘 해설: 최소 스패닝 트리 1922

안녕하세요! 개발자 여러분들을 위해 알고리즘 풀이 포스트를 작성하려고 합니다. 오늘은 백준 온라인 저지의 "최소 스패닝 트리" 문제를 다뤄보려고 합니다. 해당 문제는 주어진 그래프에서 최소 비용으로 모든 노드를 연결하는 부분 그래프를 찾는 문제입니다.

 

바로 아래 정보에서 공부해봅시다!

 

백준 알고리즘 로고

문제 내용

주어진 코드를 통해 문제의 요구사항을 파악해보겠습니다. 주어진 코드는 최소 스패닝 트리를 찾는 크루스칼 알고리즘을 구현하고 있습니다. 입력으로는 노드의 개수, 간선의 개수, 간선의 정보(시작 노드, 도착 노드, 비용)가 주어집니다. 코드는 주어진 간선들을 비용에 따라 오름차순으로 정렬한 후, 크루스칼 알고리즘을 통해 최소 스패닝 트리의 비용을 구하고 출력합니다.

 

풀이 코드

pythonCopy code
import sys

input = sys.stdin.readline

# 집합을 하나로 합침
def union(parent, x, y):
    x_root = find(parent, x)
    y_root = find(parent, y)
    parent[y_root] = x_root

# 집합의 대표번호를 반환
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# union-find 초기화
def init_union_find():
    return [i for i in range(n + 1)]

n, m = int(input()), int(input())

# 크루스칼 알고리즘 - 비용에 따라 오름차순 정렬
edges = sorted([tuple(map(int, input().split())) for _ in range(m)], key=lambda x:x[2])

answer = 0
parent = init_union_find()

for a, b, cost in edges:
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        answer += cost

print(answer)

풀이 방법

주어진 코드를 통해 문제를 해결하는 방법을 살펴보겠습니다. 이 코드는 크루스칼 알고리즘을 활용하여 최소 스패닝 트리를 찾습니다.

먼저, 주어진 입력을 통해 노드의 개수 **n**과 간선의 개수 **m**을 받습니다. 이후 각 간선의 정보(시작 노드, 도착 노드, 비용)를 입력받고, 비용에 따라 간선들을 오름차순으로 정렬합니다.

크루스칼 알고리즘을 위해 Union-Find 자료구조를 초기화합니다. 각 노드를 자기 자신을 대표번호로 하는 집합으로 초기화합니다.

정렬된 간선들을 순서대로 확인하면서, 해당 간선의 시작 노드와 도착 노드의 대표번호가 같지 않은 경우에만 해당 간선을 선택하고 비용을 누적합니다. 이후 선택한 간선의 시작 노드와 도착 노드를 Union 연산을 통해 하나의 집합으로 합칩니다.

모든 간선에 대해 위 과정을 반복하면, 최소 스패닝 트리를 구성하고 그 비용을 **answer**에 저장합니다.

 

시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 주어진 간선들을 비용에 따라 정렬하는 과정과 모든 간선에 대해 Union-Find 연산을 수행하는 과정에 좌우됩니다. 간선을 정렬하는데는 O(mlogm)의 시간이 걸리며, Union-Find 연산은 최악의 경우 O(logn)의 시간이 걸립니다. 따라서, 전체적인 시간 복잡도는 O(mlogm + mlogn)입니다.

이상으로 "최소 스패닝 트리" 문제의 풀이를 마치겠습니다. 다음 포스트에서 또 다른 알고리즘 문제를 다룰 예정입니다. 감사합니다!

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음