[알고리즘] 백트래킹(Backtracking)을 알아보자

요즘 백준 문제집을 풀고있는데, 백트래킹 개념의 문제가 나와서 한번 개념을 블로그에 정리해보려고 한다. 

 

# 등장 배경

이 글을 읽고있는 분들이라면 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 유명한 완전탐색 알고리즘은 한번쯤 들어본 적이 있을 것이다. 이러한 알고리즘은 모든 가능한 경우의 수를 탐색하는 특징이 있는데, 백트래킹도 이와 비슷한 motivation을 공유한다. 즉, '가능한 모든 방법'을 탐색하는 데에 관심사가 있는 것 ! 

하지만 DFS와 BFS는 정말 모든 노드를 탐색한다. 그러다보면 해답이 될 가능성이 없는 그래프의 노드까지 "모두" 탐색하게 되는 것이다. 우리는 알고리즘 문제를 풀고있으므로, 전혀 가능성이 없는 노드는 관심이 없을 것이다.

따라서 백트래킹(Backtracking)은 이렇게 해답이 될 가능성이 없는 노드를 아예 배제하는 방법이다. 즉, 어떤 노드가 유망하지 않으면 (해답이 될 가능성이 없으면) 배제하고 그 노드의 부모노드로 되돌아 간 후 다른 자손노드를 검색하는 것이다. 가지치기를 하는 과정을 상상해보자. 

이러한 과정은 당연히 알고리즘을 푸는 입장에서는 매우 효율적이고, 환영일 것이다! 풀이 시간도 단축될 수 있다. 

 

# Details 

앞서 언급한 것처럼 백트래킹은 아예 해답이 될 가능성도 없는 노드를 가지치기해 제거하는 것이다. 모든 자식노드가 해답이 없다면, 그 부모노드는 아예 답이 없는 것이므로 유망하지 않다고 판단하고 부모노드도 배재해버린다. 그리고 보통 선입후출의 구조인 스택(stack) 자료구조를 사용한다. 즉, 스택에 넣기 전에 노드의 유망성 검사를 하는 것이다. 

그리고 앞서 백트래킹은 DFS, BFS와 motivation을 공유한다고 했다. 따라서 백트래킹은 DFS를 수행하다가, 유망한 노드를 검토하고 만약 유망한 노드라면 그대로 서브트리로 이동하고, 그렇지 않으면 백트래킹을 해 가지치기 하는 방식으로 진행된다.

 

# 예제 - N Queen 문제 

백트래킹에서 가장 많이 예로 드는 국민 예시는 당연 N-Queen 문제일 것이다. 관련 문제 풀이는 여기를 참고해주시면 된다!

 

 

 

# 관련 문제 

- 6603 로또 https://www.acmicpc.net/problem/6603  

- 1182 부분집합의 합 https://www.acmicpc.net/problem/1182

– 9095 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095

– 9663 N-Queen https://www.acmicpc.net/problem/9663