BFS(Breadth First Search) 깊이 우선 탐색

- 그래프 탐색

그래프 탐색은 하나의 노드에서 시작해 모든 노드를 한번씩 방문하는 것이다.

가장 기본적인 탐색으로 DFS, BFS가 있으며 이 글에서는 BFS를 다룬다. 이외에도 다익스트라(Dijkstra), 플로이드 와샬(Floyd Washall) 등이 있지만 기본이 되는 DFS, BFS를 정확하게 알고 넘어갈 필요가 있다.

- BFS(Bepth First Search)

방문한 노드는 큐에 담고, queue의 front에 있는 노드와 연결된 모든 노드를 탐색한다. 이 때 이미 탐색을 완료한 노드는 탐색하지 않는다. 방문한 노드와 연결된 모든 노드를 탐색했다면 queue를 pop 해주고 위 과정을 반복한다.

- 구현

나는 DFS 나 BFS 둘 중 한가지 방법으로 풀 수 있는 그래프 이론 문제들을 거의 다 BFS로 구현하여 풀었었다.
백준 2606 DFS 문제 풀이