[알고리즘] 백트래킹 해결 방법과 예시 문제

백트래킹 이란?

백트래킹은 완전탐색을 하는 과정에서 가지치기를 통해 유망하지 않은 곳은 더 이상 탐색하지 않는 알고리즘 기법을 말한다.

 

백트래킹 용어

• 유망(Promising) 하다.
  • 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 있다면 유망하다고 한다.
• 가지치기 (Pruning)
  • 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.

 

백트래킹 문제의 일반적인 해결 방법

1. 상태 공간 트리를 구한다.
2. 깊이 우선 탐색(DFS)을 이용하여 상태 공간 트리를 탐색한다.
3. 각 노드가 유망한지를 점검한다.
4. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다음 자식 노드로 간다.
5. 어떤 노드가 해당 문제의 해가 되면 탐색을 중지하고, 해를 구한다.

 

백트래킹 문제의 예시

1. N-Queen 문제 (BOJ 9663)

N-Queen 문제는 대표적인 백트래킹 문제 중 하나이다.

N-Queen 문제란 NxN 크기의 체스판 위에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다. 즉, 같은 행, 열, 대각선에 다른 퀸이 위치하지 않도록 하는 것이다.

위 예시 코드를 실행하면 4x4 크기의 체스판 위에 4개의 퀸을 배치하는 문제를 해결한 결과가 출력된다.

백트래킹을 사용한 N-Queen 문제의 시간 복잡도는 O(N!)이며, 이는 브루트 포스와 동일하다. 하지만 백트래킹은 유망하지 않은 경우를 가지치기하며, 브루트 포스보다 더 효율적으로 문제를 해결할 수 있다.

 

2. 스도쿠 (BOJ 2239)

스도쿠는 일반적인 백트래킹 문제로 유명하다. 스도쿠는 9x9 크기의 정사각형 격자판에 숫자를 채워넣는 게임으로, 각 행과 각 열, 그리고 3x3 크기의 정사각형에 중복되는 숫자가 없어야 한다.

 

3. 암호 만들기 (BOJ 1759)

암호 만들기 문제는 길이가 L인 암호를 만드는 문제로, 암호는 알파벳 소문자로만 이루어져 있으며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다.

 

4. 순열과 조합

순열과 조합은 백트래킹을 활용한 대표적인 문제 중 하나이다.

 

마치며

백트래킹은 완전탐색을 하는 과정에서 유망하지 않은 경우를 가지치기하는 코드를 통해 시간을 단축시키는 알고리즘이다.

그렇기 때문에 백트래킹을 잘하기 위해서는 순열, 조합을 활용한 완전탐색 문제를 많이 풀수록 더 잘할 수 있다.

또, 백트래킹은 DFS 방식으로 모든 경우를 탐색하기 때문에 재귀함수를 잘 짤 수 있고, 잘 이해할 수 있어야 한다.

아직 재귀로 구현한 순열, 조합에 미숙하다면 순열, 조합을 활용한 브루트포스 문제를 먼저 풀어보고 백트래킹을 하는 것을 추천한다.