[데이터 구조와 활용] 너비 우선 탐색(BFS)

1. 너비우선 탐색이란?

- 그래프 탐색 방법 중 하나로 이름 그대로 가장 가까운 정점부터 탐색하고, 그 다음으로 가까운 정점 순서대로 차례차례 탐색을 진행하는 방식

- 지하철에서 환승할 때,  목적지에 가장 적은 수의 역을 통과하는 최적의 경로를 찾는 방식과 유사함

2. BFS 탐색 원리와 큐(Queue)

- BFS는 일반적으로 큐를 통해 구현되며, 선입 선출(FIFO) 방식과 밀접한 관계가 있음

 * 큐 : 먼저 넣은 값이 먼저 나오는 데이터 구조임

 * BFS 탐색 방식 : 출발점에 가까운 정점부터 순차적으로 방문하며, 탐색이 진행됨

- BFS는 먼저 방문한 정점부터 탐색한다는 점에서 큐의 특성과 일치

3. BFS 사용 사례

- 최단 경로 탐색 : 가중치가 없는 그래프에서 두 정점 사이의 최단 경로(최소 개수의 간선을 통해 연결된 경로)를 찾고자 할 때 유용함

- 그래프의 연결된 요소 찾기 : 그래프 내에서 방문하지 않은 정점부터 BFS 탐색을 진행하고, 탐색 중 방문한 모든 정점이 하나의 연결된 요소이며, 이 과정을 반복하여 연결 요소 개수를 셀 수 있음

- SNS 친구 추천 : 친구 관계를 기준으로 가까운 단계(친구의 친구)부터 탐색하여 친구 추천 사용

- 웹 사이트 구조 탐색(웹 크롤링) : 웹 사이트의 메인 페이지에서 가까운 페이지부터 차례대로 탐색할 때 효율적

4. 구현

import collections graph = {     'A' : ['B','C','D'],     'B' : ['A','E'],     'C' : ['A','F'],     'D' : ['A','G'],     'E' : ['B','F'],     'F' : ['C','E'],     'G' : ['D']     } visited = set() order = [] queue = collections.deque() visited.add('A') queue.append('A') while queue :     v  = queue.popleft()     order.append(v)     for n in graph[v] :         if n in visited :             continue         visited.add(n)         queue.append(n) print(order)

['A', 'B', 'C', 'D', 'E', 'F', 'G']

 5. 큐의 방식 원리 설명

- 큐를 명시적으로 사용하면 BFS가 실제로 어떻게 동작하는지 직관적으로 확인할 수 있음

- 가장 먼저 추가한 정점부터 탐색하여 너비 우선 탐색 방식이 명확하게 드러남

6. BFS의 재귀 구현이 어려운 이유

- DFS와 달리 BFS는 재귀 방식으로 구현이 매우 어려움

- BFS는 가까운 정점부터 탐색하므로, 재귀 호출 스택의 특성상 깊이를 우선적으로 탐색하는 방식과 충돌하기 때문

- 따라서 BFS는 큐를 이용해 반복문으로 구현함

7. BOJ1260

import collections a, b, c = map(int, input().split()) graph = collections.defaultdict(list) for _ in range(b):     x, y = map(int, input().split())     graph[x].append(y)     graph[y].append(x) visited = set() order = [] queue = collections.deque() visited.add(c) queue.append(c) while queue :     v  = queue.popleft()     order.append(v)     for n in graph[v] :         if n in visited :             continue         visited.add(n)         queue.append(n) print(order)

4 5 1 1 2 1 3 1 4 2 4 3 4 [1, 2, 3, 4]

8. BOJ11724

import collections a, b = map(int, input().split()) graph = collections.defaultdict(list) for _ in range(b):     x, y = map(int, input().split())     graph[x].append(y)     graph[y].append(x) visited = [False] * (a+1) order = [] queue = collections.deque() res = 0 for i in range(1,a+1) :     if visited[i] :         continue     visited[i] = True     res += 1     q = collections.deque()     q.append(i)     while q :         z = q.popleft()         for g in graph[z] :             if visited[g] :                 continue             visited[g] = True             q.append(g) print(res)

6 5 1 2 2 5 5 1 3 4 4 6 2

9. BOJ2606

import collections a = int(input()) b = int(input()) graph = collections.defaultdict(list) for _ in range(b):     x, y = map(int, input().split())     graph[x].append(y)     graph[y].append(x) visited = set() order = [] queue = collections.deque() visited.add(1) queue.append(1) while queue :     v  = queue.popleft()     order.append(v)     for n in graph[v] :         if n in visited :             continue         visited.add(n)         queue.append(n) print(len(order)-1)

7 6 1 2 2 3 1 5 5 2 5 6 4 7 5