[프로그래머스/파이썬] DFS/BFS 네트워크

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

---

알고리즘 분류

• BFS

문제풀이

입력받는 computers리스트를 백준에서 주로 풀던 그래프 딕셔너리로 변환시켜주었다.
(예제#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