📘[BFS] 네트워크

문제

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

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

답안

def BFS(n, computers, com, visited):
    from collections import deque
    queue = deque([com])
    while queue:
        v = queue.popleft()
        visited[v] = True
        for c in range(n):
            if v != c and computers[v][c] == 1:
                if visited[c] == False:
                    queue.append(c)

def solution(n, computers):
    answer = 0
    visited = [ False for _ in range(n)]
    for com in range(n):
        if visited[com] == False:
            BFS(n, computers, com, visited)
            answer += 1
    return answer

풀이

DFS가 한 놈만 패는 방식이라면, BFS는 한 놈씩 때려가면서 푸는 방식임.

BFS의 동작 순서는 다음과 같다.

def BFS(n, computers, com, visited):
    from collections import deque
    queue = deque([com])
    while queue:
        v = queue.popleft()
        visited[v] = True
        for c in range(n):
            if v != c and computers[v][c] == 1:
                if visited[c] == False:
                    queue.append(c)

1. queue를 선언함.
2. queue가 존재하지 않게 될 때까지 반복.
3. queue에 저장했던 값 중 가장 첫 번째 값을 꺼냄.
4. 방문기록에 해당 값에 대한 정보를 True로 바꿈.
5. n → 0, 1, 2, … n-1 까지 순회 (computers의 index)
6. v 가 순회한 값(c)과 같지 않으면서, computers[v][c] == 1이면?
7. c에 대한 방문기록 조회 → False면?
8. queue에 c를 저장해서 다시 반복

BFS의 실행 순서를 길지만 자세하게 다시 해보면?? (n=3, computers=[[1, 1, 0], [1, 1, 0], [0, 0, 1]] 일 때만 가정

n = 3
computers = [
  [1, 1, 0],
  [1, 1, 0],
  [0, 0, 1]
]

이런 상황임.

즉, 0 ↔ 1 연결, 2는 자기 자신만 연결된 독립 노드.

solution에서 for com in range(n)를 하므로 com=0부터 시작.

1. 시작 (com = 0)
   • visited = [False, False, False]

   • BFS 시작: queue = [0]

       queue = [0]
       visited = [False, False, False]
     

2. pop (0 꺼냄)
   • v = queue.popleft() → v = 0

   • 방문처리 → visited[0] = True

       queue = []
       visited = [True, False, False]
     

3. for문 실행
   • computers[0] = [1, 1, 0]
   • c=1 연결되어 있고, 아직 방문하지 않았음.

   • queue.append(1) 수행

       queue = [1]
     

4. while문 수행 - pop (1 꺼냄)
   • v = queue.popleft() → v = 1

   • 방문처리 → visited[1] = True

       queue = []
       visited = [True, True, False]
     

5. for문 실행
   • computers[1] = [1, 1, 0]
   • c=0은 이미 방문했음 → 무시하고 넘어감

   • c=2는 연결이 안되어있음 (computers[0][2] == 0) → 아무런 추가 동작 수행 안함

       queue = []
       visited = [True, True, False]
     

6. while문 수행 → 이전 단계에서 queue에 아무 값도 안넣어 빈 상태임

    queue = []
    visited = [True, True, False]
   

   • BFS 끝 → 0번 컴퓨터를 시작으로 한 연결된 네트워크 탐색 완료
   • answer += 1
7. 다음 com = 1
   • com = 0 단계에서 visited[1] = True로 설정됨.

   • solution 단계에서 visited[1] = True이므로 넘어감.

       for com in range(n):
           if visited[com] == False:
               BFS(n, computers, com, visited)
               answer += 1
     

8. 다음 com = 2

    visited = [True, True, False]
   

   • visited[2] = False이므로 BFS 시작

    queue = [2]
    visited = [True, True, False]
   

9. pop (2 꺼냄)
   • queue.popleft() → v = 2

   • visited[2] = True 수행

       queue = []
       visited = [True, True, True]
     

10. for문 수행

    • computers[2] = [0, 0, 1] → 자기 자신밖에 없음

        for c in range(n): # v = 2
        		if v != c and computers[v][c] == 1: # computers[2][2]만 1임
        		    if visited[c] == False: # visited[0], visited[1], visited[2] 모두 True
        		        queue.append(c)
      

    • 여기서 걸림 → BFS 종료

      • computers[2][2]만 1이므로 c=2일 때만 첫 번째 if문 통과
      • visited[2] = True이므로 두 번째 if 문에서 탈락
      • BFS 종료
      • answer += 1

회고

• 동작 순서에 대해 하나하나 적으면서 하자!