[프로그래머스] 네트워크 문제 (유니온 파인드 Disjoint Set)

문제 소개

오늘 풀었던 프로그래머스 - 네트워크 문제를 정리합니다.

이 문제는 여러 컴퓨터가 연결되어 있을 때, 서로 연결된 컴퓨터들의 묶음(네트워크)의 수를 구하는 문제입니다.

문제 링크: 네트워크 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 각 컴퓨터를 하나의 그룹(네트워크)으로 생각하고, 연결된 컴퓨터끼리 같은 그룹으로 합칩니다 (Union)
2. 모든 연결 관계를 처리한 후, 최종적으로 남은 독립된 그룹(부모가 다른 것들)의 수를 세어 네트워크 개수를 구합니다.

---

해결 과정 및 코드

핵심 아이디어

1. 처음에는 컴퓨터 각각을 독립적인 그룹으로 초기화합니다.
2. 연결 정보가 1인 경우, 두 컴퓨터를 같은 그룹으로 합칩니다(union).
3. 두 컴퓨터가 이미 같은 그룹이면 아무것도 하지 않습니다.
4. 서로 다른 그룹을 합칠 때마다 네트워크 개수(answer)를 1 줄입니다.

코드

시간 복잡도 : O(N² × α(N))

• N은 컴퓨터 수 (최대 200)
• α(N)은 아커만 함수의 역함수 (거의 상수에 가까움 → 무시 가능)

결국 거의 O(N²) 시간 복잡도로 충분히 해결 가능

 

import java.util.*;

class Solution {
    public static int[] parents;

    public int solution(int n, int[][] computers) {
        int answer = n; // 초기 네트워크 수 = 컴퓨터 수
        parents = new int[n];
        init(n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (computers[i][j] == 0) continue;
                if (union(i, j)) {
                    answer--; // 새로운 연결이 발생할 때마다 네트워크 수 감소
                }
            }
        }
        return answer;
    }

    public void init(int n) {
        for (int i = 0; i < n; i++) {
            parents[i] = i; // 자신을 부모로 초기화
        }
    }

    public int find(int a) {
        if (parents[a] == a) return a;
        return parents[a] = find(parents[a]); // 경로 압축 (Path Compression)
    }

    public boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false; // 이미 같은 그룹
        parents[rootA] = rootB; // 그룹 합치기
        return true;
    }
}

추가: "왜 유니온 파인드인가?"

• 네트워크(그룹) 관리 문제라서 유니온 파인드로 해결.
• find : 어떤 컴퓨터가 속한 네트워크(그룹)의 대표를 찾는다.
• union : 서로 다른 네트워크(그룹)를 하나로 합친다.
• 경로 압축(Path Compression)을 적용하면 find 연산이 매우 빨라집니다.

만약 BFS나 DFS로 푼다면: 각 컴퓨터를 하나씩 탐색하면서 연결된 컴퓨터를 방문표시하면 됩니다.
하지만 "연결된 그룹끼리 합치는" 문제라면 유니온 파인드가 직관적임