BFS는 노드의 깊이를 따라 파고드는 DFS와 다르게,
너비를 체크하고 체크할 구간이 없을 때, 한 칸 깊어진다.
유튜브 강의를 보다가 와닿은 표현이 있었는데,
DFS가 드라마 하나를 몰아 보는 것이라면, BFS는 여러 드라마를 1화씩 보는 것이다.
아래의 < 그림 1 >을 참고하면, BFS의 탐색 순서를 확인할 수 있다.
< 그림 1 >
순서대로라고 하면 DFS보다 순서대로라고 할 수도 있겠다.
보기와 같이, 현재의 정점을 기준으로 두고 인접 노드를 탐색한다.
DFS의 경우, 1개의 깊이 조합을 체크하기에 굉장히 용이하지만, 그 깊이 만큼 탐색 비용이 든다.
재귀함수를 이용해서 자꾸 반복하게 되면 파이썬에서는 에러가 발생하기도 한다. (리미트)
< 그림 1 >의 3번 노드를 찾거나 하기에도 BFS에 비하면 너무 오래 걸린다.