[level 3] 섬 연결하기 - 42861

문제 링크

성능 요약

메모리: 9.35 MB, 시간: 0.07 ms

구분

코딩테스트 연습 > 탐욕법（Greedy）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

---

문제 풀이

문제 분석

이 문제는 $n$개의 섬과 이들을 연결하는 다리 건설 비용(costs)이 주어졌을 때, 모든 섬이 서로 통행 가능하도록 만드는 최소 비용을 구하는 문제입니다.

이는 그래프 이론에서 **최소 신장 트리(Minimum Spanning Tree, MST)**를 찾는 전형적인 문제입니다.

• 섬 (n): 그래프의 정점(Vertex) 역할을 합니다.
• 다리 건설 비용 (costs): 그래프의 간선(Edge)과 그 가중치(Weight) 역할을 합니다.
• 목표: 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되도록 하는 트리를 구성해야 합니다.

입력 형태:

1. n: 섬의 개수 (정점의 수).
2. costs: 다리 정보 리스트. 각 요소는 [섬1, 섬2, 비용] 형태입니다.

출력 형태:

• 모든 섬을 연결하는 데 필요한 최소 총 비용 (정수).

접근 방법

이 문제는 MST를 구하는 문제이며, 일반적으로 Kruskal 알고리즘 또는 Prim 알고리즘을 사용하여 해결할 수 있습니다. 제공된 코드는 Kruskal 알고리즘과 Union-Find (Disjoint Set Union, DSU) 자료구조를 조합하여 사용했습니다.

Kruskal 알고리즘의 작동 원리:

1. 모든 간선(다리)을 비용이 낮은 순서대로 정렬합니다.
2. 가장 비용이 낮은 간선부터 차례로 선택합니다.
3. 간선을 선택할 때, 이미 연결되어 있는 두 섬을 연결하여 사이클(Cycle)이 생성되는지 확인합니다.
4. 사이클을 만들지 않는 간선만 선택하고, 해당 비용을 최소 비용 합계에 더하며 두 섬을 하나의 연결된 집합으로 합칩니다.

Union-Find (DSU) 자료구조의 역할: Kruskal 알고리즘에서 가장 중요한 것은 '사이클 확인'과 '집합 합치기'를 효율적으로 수행하는 것입니다. DSU는 두 원소가 같은 집합에 속하는지(find 연산) 또는 두 집합을 합쳐야 하는지(union 연산)를 매우 빠르게 판단하고 처리할 수 있게 해줍니다.

구현 설명

제공된 코드는 Kruskal 알고리즘을 DSU를 이용하여 구현합니다.

1. 간선 비용 순으로 정렬

• costs.sort(key = lambda x: x[2]): 입력으로 주어진 costs 리스트를 다리 건설 비용(세 번째 요소, x[2])을 기준으로 오름차순으로 정렬합니다. 가장 저렴한 다리부터 검토하기 위함입니다.
• answer = 0 및 parents = {}: 최종 최소 비용을 저장할 변수와 DSU 구조를 위한 부모 노드 정보를 저장할 딕셔너리(parents)를 초기화합니다.

2. Union-Find 구조 정의 (Find 연산)

• def find(x): 특정 섬 x가 속한 집합의 대표 노드(루트)를 찾는 함수입니다.
• 만약 x가 아직 parents 딕셔너리에 없다면, 자신을 루트로 설정합니다 (parents[x] = x).
• 재귀 호출을 사용하여 루트를 찾고, **경로 압축(Path Compression)**을 적용합니다. 이는 if parents[x] != x: parents[x] = find(parents[x]) 부분으로, 한 번 찾은 루트를 해당 노드의 직접적인 부모로 설정하여 다음 탐색 속도를 높입니다.

3. Union-Find 구조 정의 (Union 연산)

• def union(a, b): 두 섬 a와 b가 속한 집합을 합치는 함수입니다.
• 먼저 find(a)와 find(b)를 호출하여 각 집합의 루트를 찾습니다.
• 두 루트가 다르다면 (if a != b:), 즉 두 섬이 아직 연결되어 있지 않다면, 한쪽 루트의 부모를 다른 쪽 루트로 설정하여 두 집합을 병합합니다 (parents[a] = b).

4. 최소 비용 선택 및 합산 (Kruskal 적용)

• 정렬된 costs 리스트를 순회합니다 (for x,y,cost in costs:).
• if not find(x) == find(y): 현재 다리를 건설하려는 두 섬 x와 y가 이미 같은 집합에 속해있는지 (find(x)와 find(y)가 같은지) 확인합니다.
• 만약 두 섬이 아직 연결되어 있지 않다면 (사이클이 형성되지 않는다면), 해당 간선을 선택합니다:
  • answer += cost: 비용을 최종 합계에 추가합니다.
  • union(x,y): 두 섬을 연결하여 하나의 집합으로 만듭니다.
• 모든 간선을 확인한 후, answer를 반환합니다.

⏱복잡도 분석

$V$를 섬의 개수 ($n$), $E$를 다리 정보의 개수 (costs의 길이)라고 가정합니다.

시간 복잡도:

1. 정렬 단계: costs 리스트를 비용 순으로 정렬하는 데 $O(E \log E)$의 시간이 소요됩니다.
2. DSU 연산 단계: Kruskal 알고리즘은 $E$개의 간선을 모두 순회하며 DSU 연산(Find와 Union)을 수행합니다. 경로 압축과 랭크(혹은 크기) 유니온이 적용된 DSU 연산은 사실상 $O(1)$에 가까운 시간 복잡도를 가집니다 (엄밀히는 아커만 함수의 역함수 $\alpha(V)$). 따라서 총 DSU 연산 시간은 $O(E \cdot \alpha(V))$ 입니다.
3. 전체 시간 복잡도: 정렬 단계가 지배적이므로, 최종 시간 복잡도는 $O(E \log E)$ 입니다. (제한 사항에서 $E$는 최대 $O(V^2)$입니다.)

공간 복잡도:

1. 부모 딕셔너리 (parents): 최대 $V$개의 섬 정보를 저장해야 하므로 $O(V)$의 공간이 필요합니다.
2. 전체 공간 복잡도: $O(V)$ 입니다.

핵심 포인트

1. 최소 신장 트리 (MST) 문제 인식: 모든 섬을 최소 비용으로 연결하는 문제는 MST를 찾는 고전적인 문제임을 파악하고 Kruskal 또는 Prim 알고리즘을 적용해야 합니다.
2. Kruskal 알고리즘의 적용: 비용이 낮은 간선부터 우선적으로 선택하는 그리디(탐욕적) 전략을 사용하며, 이를 위해 입력 간선 리스트를 비용 순으로 반드시 정렬해야 합니다.
3. Union-Find (DSU) 구조의 효율적 사용: Kruskal 알고리즘에서 사이클 형성 여부를 빠르게 판단하고 연결된 집합을 효율적으로 병합하기 위해 DSU 자료구조(특히 경로 압축 최적화가 적용된 find 함수)를 구현하는 것이 핵심입니다.

풀이 코드

def solution(n, costs):
    costs.sort(key = lambda x: x[2])
    
    check = set()
    answer = 0
    parents = {}
    
    def find(x):
        if x not in parents:
            parents[x] = x
        if parents[x] != x:
            parents[x] = find(parents[x])
        return parents[x]
        
        
    def union(a,b):
        a = find(a)
        b = find(b)
        
        if a != b:
            parents[a] = b

    for x,y,cost in costs:
        if not find(x) == find(y):
            answer += cost
            union(x,y)
            
    return answer