프로그래머스

프로그래머스 섬 연결하기 풀이: 크루스칼 최소 신장 트리

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 섬 연결하기
  • 출처: 프로그래머스 코딩테스트 연습, 탐욕법(Greedy)
  • 자체 판단 난이도: Level 3

모든 섬이 서로 이동 가능하도록 다리를 선택하면서 총 비용을 최소화해야 한다. 비용이 낮은 간선부터 선택하되 사이클을 만들지 않아야 하므로, 크루스칼 알고리즘과 Union-Find를 함께 이해해야 해 Level 3으로 판단했다.

1. 문제 요약

n개의 섬과 섬 사이에 건설할 수 있는 다리 및 건설 비용 costs가 주어진다. 다리를 여러 번 건너더라도 모든 섬 사이에 도달할 수 있도록 만들 때 필요한 최소 비용을 반환한다.

섬을 정점, 다리를 간선, 건설 비용을 간선의 가중치로 보면 모든 정점을 연결하는 최소 가중치 연결 그래프를 만드는 문제다.

  • 섬의 수 n은 최대 100이다.
  • 같은 두 섬을 잇는 연결은 중복해서 주어지지 않는다.
  • 모든 섬을 연결할 수 있는 입력만 주어진다.
  • 직접 연결되지 않은 섬도 다른 섬을 거쳐 도달할 수 있으면 연결된 것으로 본다.

예를 들어 0-1과 1-2에 다리가 있으면 0과 2 사이에 직접 다리가 없어도 서로 통행할 수 있다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

최소 신장 트리(MST)는 모든 정점을 연결하면서 사이클이 없는 간선 n - 1개로 구성된다. 크루스칼 알고리즘은 다음 순서로 MST를 만든다.

  1. 모든 다리를 건설 비용 오름차순으로 정렬한다.
  2. 가장 싼 다리부터 확인한다.
  3. 두 섬이 이미 같은 연결 요소에 있지 않으면 해당 다리를 선택한다.
  4. 선택한 다리 수가 n - 1개가 되면 종료한다.

두 섬이 이미 같은 연결 요소에 있다면 새 다리를 선택하는 순간 사이클이 생기므로 건너뛴다.

그래프 구조와 방문 기록

현재 각 섬이 어떤 연결 요소에 속하는지 parent 배열로 관리한다. find는 한 섬의 대표 루트를 찾고, union은 서로 다른 두 루트를 하나의 연결 요소로 합친다.

경로 압축을 적용하면 find 과정에서 거쳐 간 노드가 대표 루트를 직접 가리키도록 바뀐다. 따라서 이후 같은 연결 요소인지 확인하는 작업이 빨라진다.

연결 요소를 잇는 간선만 선택하는 이유

비용이 낮은 간선을 무조건 선택하는 것이 아니라, 낮은 비용 순으로 확인하면서 연결 요소를 서로 합칠 수 있을 때만 선택해야 한다. 이미 연결된 두 섬을 다시 잇는 간선은 비용이 아무리 낮아도 새로운 섬을 연결하지 못하고 사이클만 만든다.

현재까지 선택한 간선들이 여러 연결 요소를 만들고 있을 때, 서로 다른 두 요소를 잇는 가장 싼 간선을 선택하는 것은 전체 연결에 필요한 비용을 늘리지 않는다. 이 선택을 반복하면 모든 섬을 연결하는 n - 1개의 간선이 남는다.

그리디 선택이 최적인 이유

아직 서로 다른 두 연결 요소를 잇는 후보 중 가장 비용이 작은 간선을 e라고 하자. 어떤 최적 신장 트리가 이미 e를 포함한다면 선택에 문제가 없다.

최적 신장 트리가 e를 포함하지 않는다면, e의 양 끝점을 트리 안에서 연결하는 경로가 있다. 그 경로에는 현재 두 연결 요소를 가로지르는 간선이 하나 이상 있고, 그 간선의 비용은 e보다 작지 않다. 그 간선을 제거하고 e를 넣어도 트리는 연결 상태를 유지하며 총 비용은 증가하지 않는다. 따라서 e를 선택해도 최적해를 잃지 않는다.

오답 접근과 반례

현재 섬에서 가장 가까운 다리만 반복해서 선택하거나 입력 순서대로 다리를 선택하면 전체 비용이 최소라는 보장이 없다.

n = 4
costs = [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]

비용이 낮은 0-1, 1-3, 0-2를 선택하면 총 비용은 1 + 1 + 2 = 4다. 반대로 비용이 5인 1-2를 먼저 선택하거나 이미 연결된 섬에 비용이 낮은 간선을 중복 선택하면 불필요하게 비용이 커지거나 사이클이 생긴다.

사이클 확인 없이 간선을 n - 1개 고르면 모든 섬이 연결되지 않은 상태로 끝날 수 있다. 선택한 간선 수뿐 아니라 Union-Find의 연결 요소를 함께 관리해야 한다.

시간·공간 복잡도

간선 수를 E라고 하면 간선 정렬에 O(E log E)가 필요하다. Union-Find 연산은 경로 압축을 적용하면 거의 상수 시간에 가까워 전체 순회 비용은 O(E α(n))다. 따라서 전체 시간 복잡도는 O(E log E)다.

parent 배열과 정렬된 간선 목록을 사용하므로 추가 공간 복잡도는 O(n + E)다.

3. 문제 해결 코드 (Python)

def solution(n, costs):
    parent = list(range(n))

    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]

    answer = 0
    selected = 0

    for start, end, cost in sorted(costs, key=lambda edge: edge[2]):
        root_start = find(start)
        root_end = find(end)

        if root_start == root_end:
            continue

        parent[root_end] = root_start
        answer += cost
        selected += 1

        if selected == n - 1:
            break

    return answer

find(start) == find(end)이면 두 섬이 이미 같은 연결 요소에 속하므로 해당 간선을 건너뛴다. 서로 다른 루트라면 한쪽 루트를 다른 쪽에 연결하고 비용을 더한다.

n = 1인 경우 선택해야 할 다리가 없으므로 selected == n - 1 조건을 만족한 상태로 순회가 끝나 0을 반환한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 사이클을 건너뛰며 최소 비용을 고르는지 확인할 수 있다.

assert solution(4, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]) == 4
assert solution(1, []) == 0

4. 공식 예제와 추가 검증

공식 예제와 섬 하나, 더 싼 간선이 사이클을 만드는 경우를 Python 코드로 실행했다.

공식 예제

입력:
n = 4
costs = [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]

기대 출력: 4
확인 결과: 통과
검증 목적: 사이클을 제외하면서 최소 비용 간선 3개를 선택하는지 확인

추가 검증 1: 섬 하나

입력: n = 1, costs = []
기대 출력: 0
확인 결과: 통과
검증 목적: 이미 모든 섬이 연결된 최소 입력 확인

추가 검증 2: 세 섬의 직접 연결과 우회 연결

입력: n = 3, costs = [[0, 1, 1], [1, 2, 2], [0, 2, 10]]
기대 출력: 3
확인 결과: 통과
검증 목적: 가장 싼 두 간선으로 우회 연결하는 것이 최적인지 확인

추가 검증 3: 사이클을 만드는 간선 건너뛰기

입력: n = 4, costs = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 10]]
기대 출력: 3
확인 결과: 통과
검증 목적: 이미 연결된 두 섬을 잇는 마지막 고비용 간선을 선택하지 않는지 확인

5. 다른 풀이 방식 검색 및 비교

프림 알고리즘을 사용하면 하나의 섬에서 시작해 현재 연결된 영역과 바깥 영역을 잇는 가장 싼 간선을 반복해서 선택할 수도 있다. 이 글에서는 모든 간선을 비용순으로 정렬한 뒤 사이클만 빠르게 제외하는 크루스칼과 Union-Find를 선택했다. 입력 간선을 한 번 정렬하고 처리하는 흐름이 문제 조건과 잘 맞는다.

마무리

섬 연결하기는 모든 섬을 연결하는 최소 신장 트리를 만드는 문제다. 다리를 비용순으로 확인하고 Union-Find로 사이클 여부를 판정하면, 연결을 실제로 시뮬레이션하지 않고도 최소 비용을 계산할 수 있다. 서로 다른 연결 요소를 잇는 간선만 선택하고 n - 1개가 모이면 종료하는 것이 핵심이다.

#그리디#프로그래머스#난이도 3