[프로그래머스 알고리즘 고득점 Kit][깊이/너비 우선 탐색(DFS/BFS)][Java] 네트워크

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

프로그래머스

 

정답 코드

 

그래프를 만들어서 각 숫자마다 bfs로 연결된 부분을 방문체크를 하고 
0 ~ n-1 에서 bfs 메서드가 발동된 부분을 세어주면된다.

나는 이 방법보단 유니온파인드(분리집합)이 먼저 생각이 들었기 때문에 

각 연결점을 union 해주고
부모노드를 저장하는 p 배열의 루트의 갯수(음수로 랭크를 관리)가 네트워크의 갯수가 된다.

import java.util.*;

class Solution {
    
    int[] p;
    
    public int solution(int n, int[][] computers) {
        p = new int[n]; Arrays.fill(p, -1);
        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);
                }
            }
        }
        int ans = 0;
        for(int i=0; i<n; i++) {
            if(p[i] < 0) {
                ans++;
            }
        }
        return ans;
    }
    public int find(int x) {
        if(p[x] < 0) return x;
        
        return p[x] = find(p[x]);
    }
    public void union(int x, int y) {
        int u = find(x);
        int v = find(y);
        if(u == v) return;
        
        if(p[u] > p[v]) {
            int t = u;
            u = v;
            v = t;
        }
        
        if(p[u] == p[v]) p[u]--;
        
        p[v] = u;
    }
}

유니온 파인드 이론

유니온파인드 | 분리집합 | 디스조인트셋