[BFS] 프로그래머스 LV3. 네트워크

📜 LV3. 네트워크

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

from collections import deque
def solution(n, computers):
    
    def BFS(root):
        q = deque()
        q.append(root)
        
        while(q):
            x = q.popleft()
            visited[x] = True
            for j in range(root, n):
                if (computers[x][j] and not(visited[j])):
                    q.append(j)
                    
                    
    answer = 0
    visited = [False for i in range(0, n)]
    for i in range(0, n):
        if not (visited[i]):
            BFS(i)
            answer += 1
        
    return answer

😕 어떻게 풀었지?

예시를 들어보려고 한다. 다음과 같은 네트워크가 있다고 하자!
번호를 다 매겨놨다. 네트워크의 개수를 세고 싶다.
육안으로 보면 네트워크는 3개다.

• 1-2-4-5 연결된 네트워크 1개
• 3-7 연결된 네트워크 1개
• 6 혼자 1개

어떻게 풀 수 있을까? BFS로 일단 돌아보자.

for j in range(root, n):
                if (computers[x][j] and not(visited[j])):
                    q.append(j)

그림에서 1번 노드부터 시작한다. 연결된 노드를 돌아다니면서 방문처리를 하겠다. 위 코드 부분에서 방문하지 않았으면서 연결된 노드라면 계속 돈다. 그리고 이 과정이 한 번 끝나면,

for i in range(0, n):
    if not (visited[i]): #여기서 2, 4, 5, 7번 건너뛰게 됨
        BFS(i)
        answer += 1

answer를 1 증가시킨다. 네트워크 1개를 탐색한 셈이기 때문이다.

이제 다음 단계!

2번은 이미 방문처리 했으니까 건너뛰고, 3번의 BFS가 시작된다.
그러면 마찬가지로 네트워크 1개 탐색 추가로 되겠고,

6번은 혼자니까 네트워크 1개 탐색 추가로 되어서 원하는 answer값이 나오게 된다.

✅ 핵심 포인트

deque 라이브러리 불러와서 빠르게 돌리자.