[프로그래머스] 섬 연결하기 - Level 3 (Python)

📌 문제 정보

섬 연결하기 Level 3

플랫폼

프로그래머스

유형

그래프, MST, 크루스칼, 유니온-파인드

언어

Python 3

풀이 시간

약 70분

풀이 날짜

2026.06.09

문제 링크

바로가기 ↗

---

🧩 문제 요약

n개의 섬이 있고, 섬 사이를 잇는 다리를 놓는 비용 목록 costs가 주어질 때, 모든 섬이 연결되도록 다리를 놓는 최소 비용을 구하는 문제.

입력 조건:

• n: 섬의 개수
• costs: [섬a, 섬b, 비용] 형태의 다리 목록

출력 조건:

• 모든 섬을 연결하는 최소 비용 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

"최소 비용으로 모든 섬을 연결"이라는 키워드에서 MST(최소 신장 트리) 문제임을 바로 파악했다. 모든 노드를 사이클 없이 최소 비용으로 연결하는 게 MST의 정의이기 때문이다.

MST를 구현하는 방법은 크루스칼과 프림 두 가지인데, 이 문제는 간선 목록(costs) 형태로 주어졌으므로 크루스칼이 더 직관적이었다.

2단계 - 막혔던 부분

크루스칼은 매 간선마다 "사이클이 생기는가?"를 판단해야 하는데, 처음엔 이걸 리스트로 그룹을 관리하려 했다. 근데 섬이 많아지면 매번 전체 리스트를 뒤져야 해서 비효율적이라는 걸 깨달았다.

3단계 - 해결 실마리

사이클 판단을 효율적으로 하려면 Union-Find 자료구조가 필요하다는 걸 떠올렸다. Union-Find는 각 노드의 부모를 배열 하나로 관리해서, "두 노드가 같은 그룹인가?"를 거의 O(1)에 판단할 수 있다.

크루스칼 전체 흐름:

1. costs를 비용 기준 오름차순 정렬
2. 간선을 하나씩 꺼내면서 find()로 두 섬의 루트를 확인
3. 루트가 다르면 union()으로 합치고 비용 누적
4. 루트가 같으면 이미 같은 그룹 → 사이클 발생 → 스킵

Union-Find 동작 원리 상세 설명 → 유니온-파인드(Union-Find)로 집합 관리하기

크루스칼 알고리즘 개념 정리 → 최소 신장 트리(MST)와 크루스칼 알고리즘

---

✅ 최종 풀이 코드

코드 1. 섬 연결하기 최종 풀이

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


def union(a, b, cost, parent, rank):
    root_a = find(a, parent)
    root_b = find(b, parent)

    if root_a != root_b:
        if rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        elif rank[root_a] < rank[root_b]:
            parent[root_a] = root_b
        else:
            parent[root_b] = root_a
            rank[root_a] += 1
        return cost  # 연결 성공 → 비용 반환
    return 0         # 사이클 → 스킵


def solution(n, costs):
    parent = list(range(n))
    rank = [0] * n
    total = 0

    costs.sort(key=lambda x: x[2])  # 비용 오름차순 정렬

    for a, b, cost in costs:
        total += union(a, b, cost, parent, rank)

    return total

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(E log E)	간선 정렬이 병목. Union-Find는 사실상 O(1)
공간 복잡도	O(N)	parent, rank 배열 각각 N개

E = 간선 수, N = 섬의 수

---

📈 전체 흐름 추적

데이터 1. 예시 입력 처리 흐름

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

비용 기준 정렬 후:
[[0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]]

초기 상태:
parent = [0, 1, 2, 3]
rank   = [0, 0, 0, 0]
total  = 0

[0,1,1] find(0)=0, find(1)=1 → 다름 → union → parent=[0,0,2,3]  total=1
[1,3,1] find(1)=0, find(3)=3 → 다름 → union → parent=[0,0,2,0]  total=2
[0,2,2] find(0)=0, find(2)=2 → 다름 → union → parent=[0,0,0,0]  total=4
[1,2,5] find(1)=0, find(2)=0 → 같음 → 스킵
[2,3,8] find(2)=0, find(3)=0 → 같음 → 스킵

결과: 4

그림 1. 선택된 간선으로 만들어진 MST

      1
  0 ----- 1
  |        |
2 |        | 1
  |        |
  2        3

선택: [0-1:1], [1-3:1], [0-2:2]
총 비용: 4

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	그룹을 리스트로 관리하려다 사이클 판단 로직이 복잡해짐	Union-Find로 전환
2차	union() 안에서 total을 누적하려다 UnboundLocalError 발생	union()이 비용을 return하고 solution()에서 누적하도록 역할 분리
3차	통과 ✅	-

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: "최소 비용으로 모두 연결"이라는 키워드가 보이면 MST → 크루스칼 → Union-Find 순서로 사고 흐름이 이어져야 한다.
• ✏️ 새로 알게 된 것: 크루스칼은 전략(싼 간선부터 고른다)이고, Union-Find는 도구(사이클 판단)다. 두 개를 함께 써야 크루스칼이 완성된다.
• ✏️ 새로 알게 된 것: 사이클이 생긴다는 건 "이미 다른 경로로 연결되어 있다"는 뜻이므로, 그 간선은 없어도 모두 연결된 상태 = 낭비다.
• ⚠️ 실수했던 점: union() 함수 안에서 외부 변수 total을 직접 수정하려 했다. 파이썬에서 함수는 자기 스코프 밖 변수를 수정할 수 없으므로, return으로 값을 넘기고 호출부에서 누적하는 방식으로 역할을 분리해야 한다.
• 💬 한 줄 요약: MST = 크루스칼(전략) + Union-Find(도구). 싼 간선부터 고르되 사이클만 피하면 자동으로 최솟값이 된다.