[백준] 탐색(BFS/DFS) 문제풀이 링크

완전탐색 백준링크 (BFS/DFS)

링크텍스트

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

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

역추적(back tracking) 백준링크

링크텍스트

역추적: 불필요한 탐색 그만두기
더 이상 진행해도 조건에 맞는 해를 찾을 수 없는 경우에, 가장 최근에 둔 수를 무르고 다른 수를 두는 탐색을 계속 하기

결론

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