10강: 최소 비용으로 모두 연결하라, 크루스칼 알고리즘(Kruskal’s Algorithm)

4 minute read

10강: 최소 비용으로 모두 연결하라, 크루스칼 알고리즘(Kruskal’s Algorithm)

반갑습니다 여러분! 코딩 알려주는 유쾌한 가이드, 재준봇입니다.

다들 지난 9강 이분 탐색 기억하시나요? 데이터를 반으로 뚝딱 자르면서 광속으로 정답을 찾아내던 그 짜릿함! 정말 효율의 끝판왕이었죠. 하지만 세상 모든 문제가 그렇게 정갈하게 반씩 나누어 해결된다면 얼마나 좋을까요? 하지만 현실은 훨씬 더 복잡하고 꼬여있기 마련입니다.

그래서 오늘 제가 준비한 10강은 바로 크루스칼 알고리즘입니다. 이름부터 뭔가 유럽 귀족 같기도 하고 어려워 보이지만, 사실 알고 보면 아주 단순하고 명쾌한 녀석입니다. 오늘 이 강의만 제대로 들으시면 여러분은 최소 비용으로 네트워크를 설계하는 천재 설계자가 되실 수 있습니다.

이번 시간의 미션: 우주 정거장 인터넷 망 구축하기

자, 여러분이 이제 막 취업한 우주 건설 회사의 수석 엔지니어라고 상상해 보세요. 회장님이 갑자기 말도 안 되는 미션을 줍니다.

“재준봇! 지금 우주에 흩어져 있는 5개의 정거장들이 있는데, 이 정거장들이 서로 통신이 가능하게 인터넷 케이블을 깔아야 해. 그런데 예산이 부족하니까, 모든 정거장이 연결만 된다면 총 비용이 가장 적게 드는 방법으로 케이블을 설치해 줘!”

여기서 핵심은 모든 정거장이 ‘어떻게든’ 연결만 되면 된다는 겁니다. A정거장에서 B정거장으로 갈 때 꼭 직통으로 갈 필요는 없어요. A에서 C를 거쳐 B로 가도 상관없습니다. 그냥 끊기지 않고 전체가 하나로 묶이기만 하면 됩니다.

문제 데이터 (케이블 설치 비용)

정거장 0 - 정거장 1: 7억 원
정거장 0 - 정거장 2: 5억 원
정거장 0 - 정거장 3: 10억 원
정거장 1 - 정거장 2: 3억 원
정거장 1 - 정거장 3: 2억 원
정거장 2 - 정거장 3: 4억 원
정거장 2 - 정거장 4: 8억 원
정거장 3 - 정거장 4: 9억 원

자, 여러분이라면 어떤 케이블부터 설치하시겠습니까? 무작정 아무거나 연결했다가는 회장님께 등짝 스매싱을 맞을 수도 있습니다. 이때 필요한 것이 바로 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 크루스칼 알고리즘입니다.

크루스칼 알고리즘, 도대체 정체가 뭐야?

쉽게 비유해 볼게요. 크루스칼 알고리즘은 한마디로 ‘가성비 집착남’ 알고리즘입니다.

전체 케이블 목록을 쭉 펼쳐놓고, 가장 싼 가격의 케이블부터 일단 집어 듭니다. 그리고 연결해 봅니다. 그다음으로 싼 것을 또 집어 듭니다. 그런데 여기서 주의할 점이 있습니다. 이미 연결된 애들끼리 또 연결해서 ‘사이클(순환 경로)’을 만들면 돈 낭비겠죠?

예를 들어, 0번-1번이 연결되어 있고 1번-2번이 연결되어 있는데 0번-2번을 또 연결할 필요가 있을까요? 이미 0번에서 1번을 거쳐 2번으로 갈 수 있는데 말이죠. 크루스칼은 바로 이 ‘중복 투자(사이클)’를 철저하게 배제하면서 가장 싼 것부터 선택하는 전략을 씁니다.

왜 이 알고리즘이 필요한가요?

실무에서는 이런 상황이 정말 많습니다.

도시 간 도로망을 구축할 때 최소 비용으로 모든 도시 연결하기
전기 회로를 설계할 때 전선 길이를 최소화하기
통신망 구축 비용 절감하기

시간 복잡도는 어떻게 되나요?

가장 중요한 건 ‘정렬’입니다. 간선(케이블)들을 비용 순으로 정렬해야 하니까요.

간선의 개수를 E라고 하면, 정렬에 $O(E \log E)$의 시간이 걸립니다.
이후 유니온 파인드(Union-Find)를 이용해 연결 여부를 확인하는 과정은 거의 상수 시간에 가깝습니다.
따라서 최종 시간 복잡도는 $O(E \log E)$가 됩니다. 정말 효율적이죠?

초보자 폭풍 질문! “재준봇님! 그냥 무조건 싼 것만 고르면 나중에 더 비싼 걸 연결해야만 하는 상황이 오지 않을까요? 처음부터 계획적으로 짜야 하는 거 아닌가요?”

재준봇의 명쾌한 답변! “오, 아주 날카로운 질문입니다! 하지만 크루스칼 알고리즘의 마법은 바로 거기 있습니다. 수학적으로 증명된 사실인데, 가장 작은 간선부터 차례대로 선택하면서 사이클만 피한다면, 결국 전체 합계가 최소가 되는 트리가 만들어진다는 것이 보장되어 있습니다. 믿고 따라오세요! 이것이 바로 그리디(Greedy) 전략의 힘입니다.”

실무 적용 전 주의사항

실무주의보 크루스칼은 간선의 개수가 적은 ‘희소 그래프(Sparse Graph)’에서 매우 강력합니다. 하지만 만약 정거장들끼리 거의 모든 경로에 케이블이 깔려 있는 ‘밀집 그래프(Dense Graph)’라면, 간선을 정렬하는 시간이 너무 오래 걸릴 수 있습니다. 이럴 때는 프림(Prim) 알고리즘이라는 다른 선택지가 있으니, 상황에 맞춰 도구를 골라 쓰는 센스가 필요합니다!

자, 이제 이론은 충분합니다. 실제 코드로 어떻게 구현하는지, 그 정답을 공개하겠습니다!

해결 방안 및 정답 코드 보기 (클릭)

해결 방안 가이드 (알고리즘 설계)

크루스칼 알고리즘을 설계하는 단계는 다음과 같습니다.

간선 리스트 만들기: 모든 케이블 정보를 (비용, 출발지, 도착지) 형태로 리스트에 담습니다.
비용 기준 오름차순 정렬: 가장 저렴한 케이블부터 선택하기 위해 비용을 기준으로 정렬합니다.
유니온 파인드(Union-Find) 준비: 각 정거장이 현재 어느 그룹에 속해 있는지 확인하고 합치기 위한 구조를 만듭니다. (7강에서 배운 내용 기억나시죠?)
간선 선택 및 연결:
- 정렬된 리스트에서 간선을 하나씩 꺼냅니다.
- 두 정거장의 루트 노드가 서로 다르다면(즉, 아직 연결되지 않았다면) 선택하고 두 그룹을 합칩니다.
- 루트 노드가 같다면 사이클이 발생하므로 무시하고 넘어갑니다.
종료 조건: 모든 정점을 연결했거나, 선택한 간선의 개수가 (정점 개수 - 1)개가 되면 종료합니다.

파이썬 구현 코드

def find(parent, i):
    """부모 노드를 찾는 함수 (경로 압축 적용)"""
    if parent[i] == i:
        return i
    parent[i] = find(parent, parent[i])
    return parent[i]

def union(parent, rank, x, y):
    """두 집합을 합치는 함수 (랭크 기반 최적화)"""
    root_x = find(parent, x)
    root_y = find(parent, y)
    
    if root_x != root_y:
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
        return True
    return False

def kruskal(n, edges):
    # 1. 간선들을 가중치(비용) 기준으로 오름차순 정렬
    edges.sort(key=lambda x: x[2])
    
    parent = [i for i in range(n)]
    rank = [0] * n
    mst = [] # 최소 신장 트리 결과
    total_cost = 0
    
    for u, v, weight in edges:
        # 2. 사이클이 발생하지 않는 경우에만 간선 선택
        if union(parent, rank, u, v):
            mst.append((u, v, weight))
            total_cost += weight
            
        # 모든 정점이 연결되면 조기 종료 (간선 개수 = n-1)
        if len(mst) == n - 1:
            break
            
    return mst, total_cost

# --- 테스트 데이터 ---
# 정점 개수: 5개 (0번 ~ 4번 정거장)
nodes_count = 5
# (출발, 도착, 비용)
edge_list = [
    (0, 1, 10), (0, 2, 6), (0, 3, 5),
    (1, 3, 15), (2, 3, 4), (3, 4, 2)
]

result_mst, cost = kruskal(nodes_count, edge_list)

print(f"최소 비용 연결 경로: {result_mst}")
print(f"총 최소 비용: {cost}")

코드 설명

find 함수: 내가 속한 그룹의 대장이 누구인지 찾는 과정입니다. 경로 압축을 통해 다음번 찾기 속도를 비약적으로 높였습니다.
union 함수: 두 그룹을 하나로 합칩니다. 이때 랭크(깊이)가 낮은 트리를 높은 트리 밑에 붙여 트리가 너무 길어지는 것을 방지합니다.
kruskal 함수:
- 먼저 비용이 싼 간선부터 탐욕적으로 선택합니다.
- union 결과가 True라는 것은 두 정점이 서로 다른 그룹에 있었다는 뜻이며, 이를 연결해도 사이클이 생기지 않는다는 의미입니다.
- 이렇게 선택된 간선들의 합이 바로 최소 비용이 됩니다.

이 방법을 사용하면 복잡하게 얽힌 네트워크 속에서도 가장 효율적인 연결 방법을 찾아낼 수 있습니다. 정말 놀랍지 않나요?

<hr>

💬 궁금한 점이 있다면 자유롭게 댓글을 남겨주세요! (AI 비서가 답변해 드립니다 🤖)

Twitter Facebook LinkedIn