[プログラマー/Python]DFS/BFSネットワーク

https://programmers.co.kr/learn/courses/30/lessons/43162

アルゴリズム分類

BFS

問題を解く

入力したパソコンのリストを白駿が主に解読したグラフに変換した.
(例#1−>{0:[1],1:[0],2:[]})
その後,bfs関数により未アクセスのコンピュータ面に接続されたすべてのコンピュータにアクセス処理を行う.
この関数を出力する回数は、ネットワークの個数です.

ソースコード

def solution(n, computers):
    from collections import deque
    
    graph={i:[] for i in range(n)}
    for i in range(n):
        for j in range(n):
            number=computers[i][j]
            if i!=j and number==1:
                graph[i].append(j)
    
    visited=[0]*n

    def bfs(x):
        queue=deque([x])
        while queue:
            now=queue.popleft()
            for i in graph[now]:
                if visited[i]==0:
                    visited[i]=1
                    queue.append(i)

    cnt=0
    for i in range(n):
        if visited[i]==0:
            bfs(i)
            cnt+=1
    return cnt