ネットワーク

質問する

ネットワークとは、コンピュータ間で情報を交換する接続形式を指す.例えば、コンピュータ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.

I/O例

ncomputersreturn3[[1, 1, 0], [1, 1, 0], [0, 0, 1]]23[[1, 1, 0], [1, 1, 1], [0, 1, 1]]1

I/O例説明

例1
次の2つのネットワークがあります.

例2
次のようにネットワークがあります.

問題を解く

しょかい

def solution(n,computers):
	answer=0
    queue=[0]*n
    
    def recur(com,que,a):
    	if que==0:
        	que[a]=1
        for j in range(n):
        	if com[a][j]==1 and que[j]==0:
            	recur(com,que,j)
    
    while 0 in queue:
    	for i in range(n):
        	if queue[i]==0:
            	recur(computers,queue,i)
                answer+=1
    
    return answer

2番目の解

def solution(n, computers):
    answer = 0
    stack=[0]*n
        
    def dfs(root):
        if stack[root]==1:
            return
        stack[root]=1
        for i in range(n):
            if computers[root][i]==1 and root!=i:
                dfs(i)
        
    for i in range(n):
        if stack[i]==0:
            dfs(i)
            answer+=1
        
    return answer

computers中には双方向graphの形態があるため、直接n個の繰り返しゲートを利用して接続するすべてのノードを探索する.

stackというアクセスリストを作成し、dfs関数の起動時にアクセスしたノードであるかを確認します.来訪者照還、非来訪者はstack[root]=1で来訪を示す.

該当ノードに接続されているノードにアクセスするため、重複文を迂回するcomputers[root][i]値1本人ノードでなければ再度dfs関数が次のノードにアクセスする.

接続されているすべてのノードにアクセスするとreturn最初for / if 문に戻るのでanswer+=1ネットワーク個数の計算を行います.

アルゴリズムを初めて勉強したときにネットを参考にした解答です.
何を使っているのか分からない鬼が何を書いているのかコード
2番目のコードは,ある程度のBFS/DFS概念を把握して解読したコードである.2つ目の問題かもしれませんが、すぐに解決できます.
原理が同じなので、似たようなコードは偽物です.