[プログラマレベル3]ネットワーク



に質問


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

せいげんじょうけん

  • コンピュータの数nは、1つまたは複数の200以下の自然数である.
  • 各コンピュータは、0からn−1までの整数として表される.
  • コンピュータ番号が
  • iの場合、コンピュータ[i][j]は1として表される.
  • コンピュータ[i][i]は常に1である.
  • 💡 に答える

    class Solution {
        fun solution(n: Int, computers: Array<IntArray>): Int {
            var answer = 0
            var visited = BooleanArray(n) { i -> false }
            
            computers.forEachIndexed { index, computer ->
                if(!visited[index]) {
                    dfs(index, computers, visited)
                    answer++
                }
            }
            
            return answer
        }
        
        fun dfs(i: Int, computers: Array<IntArray>, visited: BooleanArray) {
            visited[i] = true
            
            computers.forEachIndexed { j, computer -> 
                if(!visited[j] && computers[i][j] == 1)
                    dfs(j, computers, visited)
            }
        }
    }
    初めてdfsを勉強したので、難しすぎます.