DFS와 BFS(2)

BFS

너비 우선 탐색이다. 가까운 노트부터 점진적으로 탐색해 가는방법이다.

[탐색의 순서] 1->2->3->8->7(부모2)->4(부모3)->5(부모3)->6(부모7)

BFS는 탐색노드의 근접한 노드를 확인하고 그 다음 근접노드를 구해가는 특징을 따라 Queue와 함께 쓰인다.

구현방식

1. 탐색노드를 Queue에 넣는다.

2. 인접노드도 Queue에 넣는다.

위 과정을 반복한다.

정리하자면 결과가 도출되는 여러 경우의 수중에 한 경우씩 확인해 보는게 DFS, 각 경우의 수를 순서대로 확인해가는게 BFS 이다.

BFS는 재귀를 쓰는 DFS보다는 속도가 빠르다는 사실은 참고로 기억해두자.