[Algorithm] 🌐プログラムネットワーク

0、問題

ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.
せいげんじょうけん
コンピュータの個数nは、1又は複数の200以下の自然数である.
各コンピュータは0からn−1までの整数で表される.
i番コンピュータがj番コンピュータに接続されている場合、コンピュータ[i][j]は1として表される.
コンピュータ[i][i]は常に1.

1.アイデア

💡 BFS
💡 コンピュータ0から、接続されているすべてのコンピュータをキューに入れます.
💡 接続されていないコンピュータがある場合はcountを行い、新しいqueueを再作成して繰り返します.

2.コア解答

1)コンピュータ0からすべての接続されたコンピュータをキューに入れる

while(!q.isEmpty()){
            int now = q.poll();
            
            for(int idx=0; idx<n; idx++){
                if(computers[now][idx] == 1 && visited[idx] == false){
                    visited[idx] = true;
                    q.add(idx);
                }
            }
        }

2)接続されていないコンピュータがある場合はcountを行い、新しいqueueを再作成して1を繰り返す.

for(int i=0; i<n; i++){
       if(visited[i] == false) {
            	bfs(n,computers,i);
            	answer++;
            }
}

3.コード

import java.util.Queue;
import java.util.LinkedList;
class Bruteforce_2 {
    static boolean[] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for(int i=0; i<n; i++){
            if(visited[i] == false) {
            	bfs(n,computers,i);
            	answer++;
            }
        }
        
        return answer;
    }
    
    public void bfs(int n, int[][] computers, int i){
        Queue<Integer> q = new LinkedList<>();
        q.add(i);
        
        while(!q.isEmpty()){
            int now = q.poll();
            
            for(int idx=0; idx<n; idx++){
                if(computers[now][idx] == 1 && visited[idx] == false){
                    visited[idx] = true;
                    q.add(idx);
                }
            }
        }
        
    }
}

4.結果

成功