[プログラマー/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