[プログラマ/奥行き、幅優先ナビゲーション(DFS/BFS)/2]ネットワーク(JAVA)

出典:プログラマコードテスト深さ、幅優先ナビゲーション(DFS/BFS)第2題
( https://programmers.co.kr/learn/courses/30/lessons/43162 )

問題の説明

ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータAがコンピュータBに直接接続され、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.
指定されたコンピュータの個数nが、接続情報を含む2次元配列コンピュータをパラメータとする場合、ネットワークの個数を返すために解関数を記述します.

せいげんじょうけん

コンピュータの数nは、1つまたは複数の200以下の自然数である.

各コンピュータは、0からn−1までの整数として表される.

コンピュータ番号が

iの場合、コンピュータ[i][j]は1として表される.

コンピュータ[i][i]は常に1である.

解答方法

コンピュータの数に従ってブール型の配列を作成しfalseに初期化します.

0からn台のコンピュータへの繰り返しブラウズを実行します.

の繰り返し文では、コンピュータに関連するすべてのコンピュータのコンピュータをナビゲートおよび参照します.
アクセスレコード(chk配列ではtrue).
3-if. アクセスしたパソコンならスキップします.

探索終了後に1つの答えを追加します.

の答えを返します.

ソースコード

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] chk = new boolean[n];
        for(int i = 0; i < n; i++) {
            if(!chk[i]) {
                dfs(computers, chk, i);
                answer++;
            }
        }
        return answer;
    }
    void dfs(int[][] computers, boolean[] chk, int start) {
        chk[start] = true;
        for(int i = 0; i < computers.length; i++) {
            if(computers[start][i] == 1 && !chk[i]) {
                dfs(computers, chk, i);
            }
        }
    }
}

ポスト

これはdfsを用いて解決できる典型的な問題である.これは基本的なdfsを復習する良い例で、もし誰かが初めてdfsを勉強したら、私はこの問題をお勧めしたいです.