BFS란?
BFS 즉 Breath-Frist-Search는 영어를 해석한 그대로 넓이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다.
넓이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들을 퍼져가면서 탐색을 해 나간다는 뜻입니다. 스택을 이용하였던 DFS와 달리 BFS는 큐를 이용합니다. 그림 1을 보시면 이해가 더욱 쉽습니다.
그림 1에서 노드 1을 시작점으로 BFS를 수행해보겠습니다. (위 예시에서 설명을 용이하게 하기 위해 낮은 숫자부터 방문한다고 가정하겠습니다.)
- 1번을 탐색하고 난 뒤 갈 수 있는곳은 2, 3, 7 이므로 모두 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7) (큐: 2, 3, 7)
- 선입선출을 기준으로 뽑아낸 2번 노드에서 갈 수 있는 곳은 1, 3, 9이지만 이미 1, 3 은 방문처리가 되었으므로 9를 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9) (큐: 3, 7, 9)
- 선입선출을 기준으로 뽑아낸 3번 노드에서 갈 수 있는 곳은 1, 9 이지만 이미 1, 3 은 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9) (큐: 7, 9)
- 선입선출을 기준으로 뽑아낸 7번 노드에서 갈 수 있는 곳은 6, 8 이므로 모두 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9. 6, 8) (큐: 9, 6, 8)
- 선입선출을 기준으로 뽑아낸 9번 노드에서 갈 수 있는 곳은 4 이므로 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4) (큐: 6, 8, 4)
- 선입선출을 기준으로 뽑아낸 6번 노드에서 갈 수 있는 곳은 7 이지만 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4) (큐: 8, 4)
- 선입선출을 기준으로 뽑아낸 8번 노드에서 갈 수 있는 곳은 5, 7 이지만 7은 이미 방문처리가 되어있으므로 5를 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: 4, 5)
- 선입선출을 기준으로 뽑아낸 4번 노드에서 갈 수 있는곳은 9이지만 9는 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: 5)
- 선입선출을 기준으로 뽑아낸 5번 노드에서 갈 수 있는곳은 8이지만 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: )
- 큐가 비어있으므로 탐색을 종료합니다.
탐색이 되는 순서는 위와 같이 1, 2, 3, 7, 9, 6, 8, 4, 5입니다. BFS는 구현을 deque를 이용하여 합니다. 제가 공부를 했던 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with Python에서 코드를 인용하였습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
from collections import deque # deque라이브러리 사용하기 위함
def bfs(graph, visited, start):
queue = deque([start])
visited[start] = True # 시작노드 방문처리
while queue:
v = queue.popleft() # popleft로 왼쪽에서 pop함 큐와 같은 구현 위함
print(v, end = " ")
for i in graph[v]: # v와 연결되어있는 노드 중
if not visited[i]: # 방문하지 않은 노드가 있다면
visited[i] = True # 방문처리
queue.append(i) # deque에 append 해줌
graph = [
[],
[2, 3, 7],
[1, 9],
[1, 9],
[9],
[8],
[7],
[1, 6, 8],
[5, 7],
[2, 3, 4]
]
visited = [False] * 10
bfs(graph, visited, 1)
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 에라토스테네스의 체를 이용한 소수 판별 (Python) (0) | 2020.12.21 |
|---|---|
| 가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python) (0) | 2020.12.19 |
| 이진탐색 (Python) (0) | 2020.12.16 |
| bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python) (0) | 2020.12.15 |
| DFS 깊이 우선탐색 (Python) (0) | 2020.11.30 |