[プログラマー/Python]DFS/BFSネットワーク
5138 ワード
https://programmers.co.kr/learn/courses/30/lessons/43162
アルゴリズム分類
問題を解く
入力したパソコンのリストを白駿が主に解読したグラフに変換した.
(例#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
Reference
この問題について([プログラマー/Python]DFS/BFSネットワーク), 我々は、より多くの情報をここで見つけました https://velog.io/@bye9/프로그래머스파이썬-DFSBFS-네트워크テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol