BFS(넓이 우선 탐색)

• 트리나 그래프를 방문 또는 탐색하는 방법.

• 탐색 방법

  1. 루트 노드에서 시작

  2. 자식 노드들을 [1]에 저장

  3. [1] 에 저장된 노드들을 방문하고 각각의 자식들 [2] 에 저장

  4. 위 과정 반복

  5. 모든 노드 방문하면 탐색 마침

• DFS는 갈림길에서 하나의 길에 들어서서 막다른 길이 나올 떄 까지 깊게 탐색하지만 BFS는 갈림길에 연결되어 있는 모든 길을 한번 씩 탐색 뒤 다시 연결되어 있는 길을 넓게 탐색

• DFS가 한 갈래가 너무 깊게 빠져 나갈 시 시간이 너무 걸리는 것을 방지 하기 위한 방법

• 자료 구조 Queue 로 구현하는 것이 일반적 (DFS는 재귀호출)