완전탐색, BFS와 DFS

완전탐색 문제들을 풀며 백트래킹과 BFS라는 키워드를 접했는데, 내가 푼 방법들이 정확히 어떤 방법을 적용한 건지 모르겠어서, 개념을 짚고 넘어가려고 한다.

완전탐색?

내가 가진 책에서는 완전탐색을 다음과 같이 설명하고 있다.

무식하게 풀기: 모든 후보 검사하기

무식하게 풀기brute force 전략은 문제 해결을 위한 가장 단순하고도 확실한 전략입니다. 이 전략은 완전 탐색exhaustive search라고도 부르며, 답이 될 수 있는 후보를 전부 조사하여 문제를 해결합니다. 후보의 개수가 수십억 개에 달하더라도 컴퓨터의 힘을 믿고 모든 답을 하나하나 검사합니다.

직관적이고 확실하게 답을 찾을 수 있지만, 그만큼 연산의 시간복잡도가 높기 때문에(O(2**n)) 숫자가 커지면 사용하기 어렵다.

기본 완전탐색brute force는 if문과 for문만을 사용하여 전부를 검사하는 전략이지만, 완전탐색의 아이디어를 바탕으로 해 불필요한 분기branch를 제외하며 조금 더 효율적인 탐색을 하는 전략들이 있다. 그 중 내가 들었던 역추적과 DFS 기법이 포함된다.

역추적(back tracking)

역추적: 불필요한 탐색 그만두기

더 이상 진행해도 조건에 맞는 해를 찾을 수 없는 경우에, 가장 최근에 둔 수를 무르고 다른 수를 두는 탐색을 계속 하기

DFS와 BFS는 역추적의 개념을 이용한 재귀 알고리즘이다.

DFS: depth-first search: 깊이우선탐색

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. ... However, ensure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once.

DFS 알고리즘은 backtracking 개념을 사용하는 재귀 알고리즘이다. 가능한 모든 노드에 대해 완전탐색과 backtracking을 한다. ... 방문한 노드에 표시해두면, 동일한 노드를 두 번 이상 방문하는 것을 방지할 수 있다.

여기까지 찾아 보니 backtracking과 DFS의 개념에 혼동이 왔다.

그래서 다시 검색해봤다.

[참고] https://gamedevlog.tistory.com/49
https://chanhuiseok.github.io/posts/algo-23/

결론

DFS (와 BFS)는 모든 노드를 탐색하는 것을 목표로 하는 완전탐색을 베이스로 한 그래프 탐색 기법이다. 그 중 DFS는 깊이를 우선해 탐색하는 것.
문제 풀이에 적용할 때는, 가능한 모든 경우의 수를 DFS방식으로 탐색하는 중 조건을 걸어서 올바른 해가 나오지 않을 듯한 경우에 backtracking을 이용해 직전의 수를 물리고 다른 수를 두는 식으로 두 탐색 기법을 혼용하여 사용한다.

BFS

breadth-first search: 너비우선탐색

[참고] https://twpower.github.io/151-bfs-dfs-basic-problem
검색하다가 이 글을 봤는데, 글에서 소개된 문제가 내가 고민중이던 문제와 굉장히 비슷한 문제였다.
[백준] 2667 https://www.acmicpc.net/problem/2667 단지번호붙이기
[백준] 2468 https://www.acmicpc.net/problem/2468 안전영역