❓ Question
BOJ 14502 - 연구소 문제를 푸는데 문제를 읽어보니 완전 탐색을 통해 문제를 해결해야겠다고 생각했다. 하지만 완전탐색 방법을 사용하면 3중 for문을 사용하게 되어 코드가 보기 안좋을 것 같아서 백트래킹 방법을 통해서도 문제를 푸는 방향을 고민했다. 생각해보니 완전탐색이나 백트래킹이나 둘다 모든 케이스를 수행하는 알고리즘인 것 같아서 두 알고리즘 사이의 차이를 이해하고 싶어졌다.
💡 Answer
완전탐색
모든 경우를 탐색해가면서 무언가를 세거나 어떤 조건이 가능한 경우가 있는 확인하는 방법
흔히 알고 있는 DFS/BFS도 완전탐색에 해당한다.
언제 사용해야 할까?
- 발생가능한 경우의 수가 충분히 적은 경우
- 따져야 하는 상황이 특정 규칙에 따라 발생하지 않는 경우
- 각각의 경우에 따져야 하는 상황이 명확한 경우
어떻게 해결해야 할까?
- 발생가능한 모든 경우를 찾아낸다.
- 각각의 경우에 대해 조건에 부합하는지 판단한다.
백트래킹
재귀를 이용한 완전탐색 방식으로, 유망(promising)하지 않은 경로를 차단하고 목표 지점에 도달할 수 있는 가능성이 있는 경로에 대해서만 탐색을 수행하는 방법
언제 사용해야 할까?
- 완전탐색을 사용할 때의 조건을 기본적으로 만족할 때
- 초기 상태에서 목표 상태에 도달하기 위해 상태를 전이시키면서 나아갈 수 있는 경우
- 탐색 중간 시점에서 특정 경우가 조건에 부합하는 지 판단 가능한 경우
어떻게 해결해야 할까?
- 초기 상태를 설정한다.
- 목표 상태에 도달하기 위해 전이시켜야 할 상태를 생각한다.
- 상태 전이를 재귀적으로 구현한다.
- 해당 상태가 목표 상태에 도달할 수 있는지 판단하는 방법을 생각한다.
- 재귀 호출 이전 상태를 저장하고 돌아가는 방법을 고민한다.
완전탐색 vs 백트래킹
백트래킹은 완전탐색을 개선한 형태의 탐색 방식이었다. 모든 경우를 일일이 따져야하는 완전탐색의 시간복잡도의 문제를 가지치기(pruning)을 통해 개선한 방식이 백트래킹이다. 완전탐색을 통해 모든 경우를 확인하기에는 한계가 존재할 때 백트래킹 방식을 통해서 경우의 수를 줄여 문제를 해결해야 할 것 같다.
\(o_o)/