[프로그래머스/Java] Lv.3 - 네트워크(Union-Find)

📝 문제 설명

컴퓨터들의 연결 관계가 주어졌을 때, 총 몇 개의 독립된 네트워크가 존재하는지 파악하는 문제입니다.
앞서 DFS/BFS로도 해결할 수 있지만, 이번에는 집합의 합치기와 찾기 연산을 지원하는 유니온 파인드(Union-Find) 자료구조를 사용하여 풀이했습니다.

---

💡 접근 방식

1. 유니온 파인드(Union-Find) 선정

그래프의 '연결 요소(Connected Component)'를 찾는 문제는 결국 "어떤 노드들이 같은 집합에 속해 있는가"를 묻는 것과 같습니다. 유니온 파인드는 여러 개의 노드가 있을 때 선택한 두 노드가 같은 집합인지 확인하고, 하나로 합치는 데 최적화된 알고리즘입니다.

2. 경로 압축 (Path Compression)

find 함수를 구현할 때 단순히 부모를 찾아가는 것에 그치지 않고, unf[v] = find(unf[v])와 같이 재귀적으로 루트 노드를 찾아 부모 배열을 업데이트했습니다. 이를 통해 트리의 높이를 낮춰 탐색 효율을 $O(1)$에 가깝게 최적화했습니다.

3. 네트워크 개수 산출

모든 연결 관계(computers[i][j] == 1)에 대해 union 연산을 수행한 뒤, 최종적으로 unf 배열을 순회합니다. 이때 부모가 자기 자신인 노드(unf[i] == i)의 개수를 세면, 그것이 곧 독립된 집합(네트워크)의 총 개수가 됩니다.

---

💻 구현 코드

import java.util.*;

class Solution {

    static int[] unf;
    
    public int find(int v) {
        if(unf[v] == v) return v;
        else return unf[v] = find(unf[v]);
    }
    
    public void union(int a, int b) {
        int x = find(a);
        int y = find(b);
        if(x != y) unf[x] = y;
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        unf = new int[n];
        for(int i=0; i<n; i++) {
            unf[i] = i;
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(computers[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        
        for(int i=0; i<n; i++) {
            if(i == unf[i]) answer++;
        }
        
        return answer;
    }
}

---

✨ 느낀 점

✅ 탐색 vs 관계
DFS가 그래프의 간선을 타고 '이동'하며 방문하는 방식이라면, 유니온 파인드는 노드 간의 '관계'를 집합 단위로 정의한다는 차이점을 확실히 이해하게 되었습니다. 탐색 로직이 따로 필요 없어서 코드가 구조적으로 명확해지는 장점이 있었습니다.

✅ 최적화의 중요성 (경로 압축)
단순히 부모를 리턴하는 것과 unf[v] = find(unf[v])를 통해 부모를 갱신하는 것의 성능 차이를 다시금 체감했습니다. 데이터가 방대해질수록 트리가 편향되는 것을 막아주는 경로 압축 기법은 유니온 파인드의 꽃이라고 생각합니다.

✅ 문제 해결의 다양성
하나의 문제를 DFS, BFS, 그리고 유니온 파인드로까지 풀어보면서 알고리즘을 선택하는 시야가 넓어졌습니다. 효율성과 정확성을 동시에 요구하는 환경에서 상황에 맞는 최적의 도구를 꺼낼 수 있는 자신감이 생겼습니다.