프로그래머스 등급3 - 섬 연결하기

섬 연결하기 문제 바로 가기

풀이 날짜: 2026-05-01

baekjoon 알고리즘 문제 풀이

풀이 코드


def solution(n, costs):
    
    def find_parent(parent,x):
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]
    
    def union_parent(parent,a,b):
        a = find_parent(parent,a)
        b = find_parent(parent,b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    parent = [0] * n
    
    for i in range(n):
        parent[i] = i
        
    costs.sort(key=lambda x:x[2])
    
    answer = 0
    
    for a,b,cost in costs:
        if find_parent(parent,a) != find_parent(parent,b):
            union_parent(parent,a,b)
            answer += cost
    
    return answer

문제 핵심

처음에는 DFS나 플로이드 워셜처럼 “연결 여부”나 “최단 거리”를 구하는 방식으로 접근하려고 했다. 하지만 이 문제는 단순히 섬이 연결되어 있는지를 확인하는 문제가 아니라, 모든 섬을 연결하면서 총 비용의 합이 최소가 되도록 해야 하는 문제였다. 따라서 핵심은 “최소 비용으로 전체를 연결”하는 것이고, 이는 최소 신장 트리(MST) 문제라는 것을 알게 되었다.

접근 방법 (아이디어)

이 문제에서는 비용이 가장 작은 다리부터 선택해 나가는 Kruskal 알고리즘을 사용했다. 다만 무조건 비용이 작은 다리를 선택하면 안 되고, 이미 연결된 섬끼리 다시 연결하면 사이클이 생기므로 이를 방지해야 했다. 따라서 두 섬의 부모 노드를 확인해 아직 같은 그룹이 아닐 때만 연결하도록 구현했다.

Union-Find 사용 이유

사이클 여부를 효율적으로 판단하기 위해 Union-Find(Disjoint Set) 자료구조를 사용했다. find_parent() 함수는 특정 노드가 어떤 그룹에 속해 있는지 확인하는 역할을 하고, union_parent() 함수는 서로 다른 그룹일 경우 하나의 그룹으로 합치는 역할을 한다. 이를 통해 이미 연결된 섬인지 빠르게 판별할 수 있었다.

비용 기준 정렬이 중요한 이유

Kruskal 알고리즘의 핵심은 “가장 비용이 적은 다리부터 선택”하는 것이다. 따라서 costs.sort(key=lambda x: x[2])를 사용해 비용 기준으로 오름차순 정렬했다. 이후 가장 싼 다리부터 확인하면서, 아직 연결되지 않은 섬일 경우에만 선택해 총 비용을 누적했다.

구현 과정에서 헷갈렸던 점

이 문제가 최단 거리 문제가 아니라 최소 신장 트리 문제라는 점을 이해하기 전까지는 플로이드 워셜이나 DFS로 접근하려고 했는데, 문제의 목적 자체가 다르다는 것을 깨닫고 Kruskal 방식으로 수정했다.

Vienna sausage