BFS 알고리즘 정리

BFS(Breadth First Search)란?

BFS란 너비 우선 탐색으로도 불리며 시작 노드부터 가장 가까운 노드들을 방문하고

멀리 떨어진 노드를 나중에 탐색하는 방법이다.

DFS가 하나의 노선을 따라 종점까지 다녀오고 다시 다음 노선의 종점까지 가는 느낌이라면

BFS는 내 친구들을 하나하나 만나고 그후에 내 친구들의 친구들을 만나는걸 반복하는 느낌이다. 

---

BFS의 장점

- 출발노드에서 목표노드까지 최단경로를 보장한다.

BFS의 단점

- 경로가 매우 길 경우, 많은 기억 공간을 필요하게 된다.

 

탐색

BFS는 선입선출인 큐(Queue) 자료구조 형태를 가졌기 때문에 우선 탐색 시작 노드를 큐에 삽입과

방문처리를 한다. 그다음 큐에서 노드를 꺼낸 후 노드의 인접 노드 중 방문처리 하지 않은 노드를

모두 큐에 삽입, 방문처리 한다. 위 과정을 반복한다.

 

파이썬에서는 큐 구조를 사용하기위해 collections의 deque 라이브러리를 사용한다.

from collections import deque