[알고리즘] BFS (너비 우선 탐색)

1. BFS (Breadth-First Search) : 너비 우선 탐색

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

• BFS는 큐 자료구조를 이용하며, 구체적 동작 과정은 다음과 같음

  • 탐색 시작 노드를 큐에 삽입하고 방문처리

  • 큐에서 노드를 꺼낸 후, 해당 노드에 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하여 방문처리

  • 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복

  ---

1-1. BFS 동작 예시

• [Step 0] 그래프를 준비 (방문기준 : 번호가 낮은 인접노드부터) / 시작노드 : 1
  

---

• [Step 1] 시작노드 ‘1’을 큐에 삽입하고 방문처리
  

---

• [Step 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접노드 ‘2’, ‘3’, ‘8’을 큐에 삽입하여 방문 처리
  

---

• [Step 3] 큐에서 노드 ‘2’을 꺼내 방문하지 않은 인접노드 ‘7’ 을 큐에 삽입하여 방문 처리
  

---

• [Step 4] 큐에서 노드 ‘3’을 꺼내 방문하지 않은 인접노드 ‘4’, ‘5’ 을 큐에 삽입하여 방문 처리
  

---

• [Step 5] 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접노드가 없으므로 무시
  

---

• 위와 같은 과정을 큐가 빌 때까지 계속 반복한다.

---

1-2. BFS 동작 기본 코드

# BFS알고리즘을 구현하기 위해서 무조건 큐를 사용
from collections import deque
import sys
input = sys.stdin.readline

# BFS 함수 정의
def BFS(graph, v, visited):
	# 큐에 시작노드를 삽입
    queue = deque([v])
    # 해당 노드를 방문처리
    visited[v] = True
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = " ")
        # 시작노드인 v와 연결되어있는 노드들을 탐색
        for i in graph[v]:	
            if not visited[i]:
                queue.append(i)
                visited[i] = True

N, M, V = map(int, input().split())
# 2차원 리스트 이용(각 노드가 연결된 정보를 표현)
graph = [[] for _ in range(N+1)]	
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

    for i in range(N+1):
        graph[i].sort()

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * (N+1)
# 정의된 DFS 함수 호출
BFS(graph, V, visited)