[프로그래머스, 43162] 네트워크 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

728x90

---

메모리: 93.4 MB, 시간: 0.45 ms

사용 알고리즘: 유니온 파인드

 

먼저 유니온 파인드로 네트워크들을 모두 연결해 준다.

이후 유니온 파인드에서 사용한 parent 배열을 순회한다.

어느 한 네트워크에서 최고 조상인 parent[i] == i를 찾는다면 answer++ 해준다.

class Solution {
    
    static int[] parent;
    
    public int solution(int n, int[][] computers) {

        // 유니온 파인드로 네트워크 개수 구하기
        parent = new int[n];
        for(int i = 0; i < n; i++) parent[i] = i;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(computers[i][j] == 1) union(i, j);
            }
        }
        
        // 네트워크 개수 세기
        int answer = 0;
        for(int i = 0; i < n; i++) {
            if(parent[i] == i) answer++;
        }
        
        return answer;
    }
    
    private static int find(int a) {
        if(parent[a] == a) return a;
        
        return parent[a] = find(parent[a]);
    }
    
    private static void union(int a, int b) {
        
        a = find(a);
        b = find(b);
        
        if(a < b) parent[b] = a;
        else parent[a] = b;
    }
}