이 포스트는 책 '이것이 코딩 테스트다'를 토대로 작성하였습니다.

📌 Breadth First Search (BFS)

• 너비 우선 탐색이라고 부른다.
• 가까운 노드부터 탐색하는 알고리즘

👉 BFS 알고리즘

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

🧐 예시

다음과 같은 그래프를 노드 1을 시작으로 BFS를 이용해 탐색한다.

step 1

• 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다.
  

step 2

• 큐에서 노드 '1'을 꺼내고
  방문하지 않은 인접 노드 '2', '3', '8'을 모두 큐에 삽입하고 방문 처리를 한다.
  

step 3

• 큐에서 노드 '2'를 꺼내고
  방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 한다.
  

step 4

• 큐에서 노드 '3'을 꺼내고
  방문하지 않은 인접 노드 '4', '5'를 모두 큐에 넣고 방문 처리를 한다.
  

step 5

• 큐에서 노드 '8'을 꺼내고
  방문하지 않은 인접 노드 '6'을 큐에 넣고 방문 처리를 한다.
  

step 6

• 남아 있는 노드에 방문하지 않은 인접 노드가 없으므로
  모든 노드를 차례대로 꺼낸다.
  

✔ 결과

노드의 탐색 순서는 큐에 들어간 순서이므로,
노드의 탐색 순서는

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

이다.

⌨ BFS 코드

from collections import deque

def bfs(graph, start, visited):
    # 큐(Queue) 구현
    queue = deque([start])
    
    # 현재 노드 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        
        # 해당 원소와 인접하고 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True # 방문 처리