[問題解決]プログラマ-ネットワーク(dfs&bfs)[レベル3]

提问链接

問題の説明

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

せきぶん

dfs=>四半期終了前に(同じネットワーク上で)

をナビゲートする.

dfsで四半期ナビゲーションを完了すると、1つのナビゲーション回数

が増加する.

全ノードナビゲーション終了後、累計ナビゲーション回数はネットワーク個数!!

私の答え

基本的なdfs操作手順と同じです.dfsアクションには、次のものが含まれます.
1.ナビゲーション開始ノードのリスト(スタック)を挿入し、アクセスを処理する
2.最上位ノードにアクセスされていない隣接ノードがある場合は、リスト(スタック)に入れてアクセス処理を行います.
アクセスされていない隣接ノードがない場合は、リスト(スタック)から最上位ノードがポップアップされます.
3.完了しないまで手順2を繰り返す

コード#コード#

def dfs(computers, v, visited):
    visited[v] = 1 # 2. 방문 처리
    for i in range(len(computers)): # 3. 인접 노드 확인하기
        if computers[v][i] == 1 and visited[i] == 0: # 4. 인접노드 존재하고, 방문 안했다면
            dfs(computers,i, visited) # 탐색
            
def solution(n, computers):
    answer = 0
    visited = [0]*n
    
    for v in range(n):
        # 1. 방문 안했다면 탐색 시작
        if visited[v]==0:
            dfs(computers, v, visited)
            answer += 1
    return answer