그래프의 모든 정점을 탐색하는 방법은 여러가지가 있는데, 가장 대표적인 방법이 BFS와 DFS이다.

BFS, DFS, BackTracking? 그게 뭐에요..?

BFS

BFS(Breadth-First Search)란 너비를 우선적으로 탐색하는 완전 탐색 기법이다.
트리구조로 생각해봤을 때 현재 레벨의 노드들을 모두 탐색한 후, 그 다음 레벨의 노드들을 탐색하는 방법이라고 생각하면 된다. 이러한 이유로 BFS는 주로 그래프의 규모가 작고, depth가 얕을 때 사용한다.

DFS

DFS(Depth-First Search)란 깊이를 우선적으로 탐색하는 완전 탐색 기법이다. DFS 탐색기법은 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색하고 싶을 때 사용한다. DFS를 사용해 탐색할 경우 모든 경로를 살펴보기 전에 원하는 답을 얻어낼 수도 있고, 현재 경로가 유망하지 않다고 판단되는 순간 다음으로 넘어가게(BackTracking) 할 수도 있기 때문에 주로 그래프의 규모가 큰 경우에 사용한다.

BackTracking

백트래킹(BackTracking)이란 DFS에서 가지치기를 통해 유망하지 않은 루트로 판단될 경우 더이상 고려하지 않고 탐색하는 완전탐색 기법 중 하나이다.
어떤 노드의 유망성을 점검한 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 탐색한다.

그래서 어떻게 사용하는데요??

BFS, DFS, BackTracking의 개념에 대해 알아도 막상 사용하려고 하면 뭘 어떻게 사용해야 하는지 막막하다. BFS, DFS, BackTracking는 어느정도 공통적인 사용방법이 있다. 이 방법을 토대로, 해결해야 하는 문제에 따라 조금씩 응용해서 사용하면 된다.

(보통) 공통적으로 사용하는 것들로 방문체크배열과 정점 대기열이 있다. (정식 명칭이 아니다. 지금 설명하기 위해서 그냥 생각하기 쉽게 붙인 이름이다.)

• 방문체크배열: 해당 노드를 탐색한 적이 있는지를 저장해두는 배열. 불린 값을 저장해놓는다.
• 정점 대기열: 탐색해야할 정점들을 담아두는 대기열. Stack이나 Queue를 사용한다.

BFS

BFS는 너비 우선 탐색을 진행해야 하므로, 탐색해야할 정점 대기열로 Queue를 사용한다.

DFS

DFS는 깊이 우선 탐색을 진행해야 하므로, 탐색해야할 정점 대기열로 Stack을 사용한다.
정점 대기열을 사용하지 않고 DFS를 진행하는 방법도 있는데, 재귀를 사용하면 된다.

⚠ Stack을 사용하는 방법과 재귀를 사용하는 방법 모두 DFS를 진행하는 방법인 것은 맞지만 탐색 순서에는 차이가 있다.

BackTracking

BackTracking은 재귀를 이용한 DFS와 가지치기를 함께 사용한다. 또, 백트래킹은
방문여부를 체크하는 대신 유망성을 체크해야 한다.