[프로그래머스] 네트워크 - JAVA

문제

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

프로그래머스

 

코드

1. Union-Find로 풀이

class Solution {
    int arr [];
    public int solution(int n, int[][] computers) {
        arr = new int [n];
        
        for(int i=0;i<n;i++){
            arr[i] = i;
        }
        
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(computers[i][j] == 1){
                    union(i, j);
                }
            }
        }
        int answer = 0;
        for(int i=0;i<n;i++){
            if(arr[i] == i){
                answer++;
            }
        }
        return answer;
    }
    
    public void union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        arr[bRoot] = aRoot;
    }
    
    public int find(int a){
        if(arr[a] == a) return a;
        else return arr[a] = find(arr[a]);
    }
    
}

 

2. bfs 로 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = bfs(n, computers);
        return answer;
    }
    
    public int bfs(int n, int[][] computers){
        boolean visited[] = new boolean [n];
        
        int count = 0;
        for(int i=0;i<n;i++){
            if(visited[i]) continue;
            Queue<Integer> que = new LinkedList<>();
            que.add(i);
            visited[i] = true;
            count++;
            
            while(!que.isEmpty()){
                int s = que.poll();
                for(int d=0;d<n;d++){
                    if(s == d) continue;
                    if(computers[s][d] == 1){
                        if(!visited[d]){
                            que.add(d);
                            visited[d] = true;
                        }
                    }
                }
            }
        }
        System.out.println(count);
        return count;
    }
}