Algorithm BFS(Breadth-first search)

알고리듬 BFS(Breadth-first search)를 알아보겠습니다.

BFS는 너비 우선 탐색인데요. 2진 트리가 있을 때 너비를 우선 탐색하는 것을 말합니다.
BFS는 Queue 자료구조를 이용하여 쉽게 탐색할 수 있습니다.
​
아래와 같은 트리가 있다고 봅시다.

너비 우선 탐색은 내려가기 전에 너비를 한 번 쫙 훑어보는 것을 말합니다.

탐색 순서는 이렇게 됩니다.

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

뭐 사람에 따라서는 이렇게 하기도 하겠죠.

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

어떤 식으로 하든 같은 계층에 있는 노드를 다 방문하기 전에는 아래로 내려가지 않는다는 점 꼭 기억해 주세요.

코드로 한 번 보겠습니다.

Python에서 deque을 사용합니다.

queue는 스레드를 신경 쓰고, deque는 스레드를 신경 쓰지 않기 때문에 속도적인 측면만 필요하다면 queue보다는 deque을 사용하는 게 좋습니다.

12 번째 줄처럼 탐색에 사용할 deque(덱)를 하나 만듭니다.

13 번째 줄처럼 root를 집어 넣습니다.

15 번째 줄에서 덱이 비어있지 않다면 계속 탐색을 하도록 합니다.

16 번째 줄에서 현재 덱에 들어있는 크기를 구하고, 18 번째 줄처럼 그 크기만큼 반복합니다.

19 번째 줄처럼 덱에 들어있는 노드를 꺼내어 다음에 탐색할 왼쪽, 오른쪽 노드들을 덱에 넣습니다.

끝.

카테고리: Algorithm