BFS와 DFS는 그래프의 각 노드를 순회하는 알고리듬이다.
중복 방문을 허용하지 않거나 부분적으로만 허용하는 경우, 최대 깊이가 유한한 경우, 모든 정점을 방문할 수 있다.
그래프의 노드를 탐색하는 것은 중요하다. 특히 많은 알고리듬에서는 데이터가 그래프로 주어지지 않는 경우에도 모든 경우의 수를 그래프 형태로 변형하여 분석하는 경우가 많다. 예를 들면 이런 문제
https://www.acmicpc.net/problem/17114
는 대표적인 그래프 순회 문제로 알려져 있다. 흥미 있다면 풀어보는 것도 좋다.
모든 노드를 적절한 반복문을 통하여 모두 해결하고자 하는 방법은 가능할 수도 있지만, 모든 가능한 문제의 입력에 대해서 잘 작동한다는 보장이 없고, 잘 작동할 만큼 많은 경우의 수를 계산하는 것은 그만큼 큰 시간을 요구한다. (계산하는 데 시간이 걸린다는 점도 물론 포함되겠지만 로직을 잘 작성할 수 있는 최소 크기의 커버의 크기가 매우 크다는 것이 가장 중요한 포인트이다.)
BFS는 방문한 깊이가 1인 노드를 모두 방문하고, 깊이가 2인 노드를 모두 방문하고, 깊이가 3인 노드를 모두 방문하고... 와 같은 방식으로 모든 노드를 순회한다. 깊이가 n+1인 노드는 모두 깊이가 n인 노드와 간선으로 연결되어 있기 때문에 어떤 노드의 깊이 정보 없이도 모든 노드를 깊이 순서대로 방문할 수 있고, 방문 순서는 깊이에 따라 정렬되어 있으므로 경로에 관계없는 가중치 없는 최단거리를 구하는 데 유용하게 쓰인다.
DFS는 가장 최근에 방문한, 방문하지 않은 자식노드가 있는 노드를 우선 방문하는 방식으로 모든 노드를 순회한다. DFS는 이전 단계로 되돌아가면 이 노드를 방문하기 위해 필요한 다른 노드를 알 수 있다. 즉, 다시 루트까지 되돌아가는 과정을 통해 어떤 노드까지 도착하기 위한 경로를 알 수 있다. 거리에 관계없는 경로를 구하는 데 유용하게 쓰인다.
BFS는 큐 구조를 사용한다. 큐 구조는 먼저 예약된 아이템을 먼저 사용하는 구조인데, 어떤 노드를 방문할 때 이후 방문할 노드로 현재 노드의 자식 노드들을 예약할 때 이전에 예약된 노드의 순서를 바꾸지 않는다. 루트 노드에 대해서 깊이가 1인 노드를 모두 큐에 집어넣게 되고, 깊이가 1인 노드를 방문할 때 마다 깊이가 2인 노드를 깊이가 1인 노드 이후에 방문할 것으로 예약하고, ... 깊이가 n인 노드를 방문할 때 마다 깊이가 n+1인 노드를 깊이가 n인 노드 이후에 방문할 것으로 예약하는 식으로 깊이 순서대로 방문하게 된다.
한편 DFS는 스택 구조를 사용하는데, 나중에 예약된 아이템을 먼저 사용하는 구조이다. 어떤 노드를 방문할 때 자식 노드들을 스택에 집어넣으면, 그 노드와 같은 깊이의 노드보다 자식 노드를 먼저 방문하게 된다. 그리고 자식노드를 가장 우선적으로 방문하게 되므로 직전에 방문한 노드가 부모 노드가 된다. 유일한 해를 찾거나, 여러 해 중 하나만 찾아도 충분한 경우 방문 방법을 알기 위해서 DFS를 사용할 수 있다. 또한 BFS에서는 불가능한, 그래프가 가중치를 가지는 상황에서도 탐색할 수 있다.
