백트래킹(Backtracking)

백트래킹(Backtracking)이란?

• 제약 조건(constraints)을 가진 최적화 문제, 결정 문제를 푸는 방법 중 하나로 퇴각 검색이라고도 부른다.
• 완전 탐색(brute force)과 비슷하게 모든 경우의 수를 시도한다.
• 탐색 과정에서 현재 경로(해, solution)가 조건을 만족하지 못할 것 같다면 배제하고 이전 단계로 돌아간다.
  • 해가 될 가능성이 있는 해를 유망하다(promising)고 한다.
  • non-promising한 해를 제외하는 것이라고도 할 수 있으며, 이를 가지치기(pruning) 라고도 부른다.
• 일반적인 완전 탐색에 비해 탐색해야 하는 경우의 수가 줄어들게 된다.

 

일반적으로 DFS를 이용해 구현하며,

탐색 과정에서 제약 조건을 걸어

만약 해당 조건을 만족 시키지 못한다면 이전 Node(분기)로 돌아오는 방법을 사용한다.

 

DFS(Depth First Search)와 그래프 사이클 찾기

 

 

백트래킹 예제 1 - 백준 15649번: N과 M

N과 M 시리즈는 가장 쉬운 백트래킹 예제 중 하나이다.

 

15649번: N과 M (1)

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
    - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

1부터 N까지의 각 수를 '노드'로 본다면, 모든 노드끼리 서로 '엣지'가 연결된 형태의 그래프로 볼 수 있다.

 

노드의 유망성 판단 조건

• 새로 탐색할 노드는 지금까지의 경로와 중복이 아닌 노드여야 한다.
• 호출이 끝나지 않은 노드는 calling[node] = true로 설정, 호출이 끝났거나 호출이 되지 않은 노드는 false로 설정한다.
• 만약 지금까지의 calling[node] == true 인 노드가 있다면 해당 노드는 탐색하지 않는다. => dfs를 호출하지 않는다.

 

탐색 종료 조건

• 탐색한 경로의 노드 수가 M개가 되면 탐색을 종료한다.

#include <iostream>

using namespace std;

int N, M;

void dfs(int cnt, int buf[], bool calling[]) {
  // 탐색한 노드의 수가 M개가 되면 종료한다.
  if (cnt == M) {
    for (int i = 1; i <= M; i++) {
      cout << buf[i] << " ";
    }
    // **주의** 여기서 endl을 사용하면, 해당 라인에서 즉시 flush가 되므로 타임아웃이 난다.
    // endl 대신 개행문자를 써주자.
    cout << "\n";
    return;
  }

  for (int i = 1; i <= N; i++) {
    //호출이 끝나지 않은 경우 (이미 나온 숫자인 경우) 탐색하지 않는다.
    if (calling[i] == true) continue;  
    calling[i] = true;
    buf[cnt + 1] = i;
    dfs(cnt + 1, buf, calling);
    
    // 호출이 끝나면 다시 calling을 false로 변경한다.
    calling[i] = false;
  }
}

int main() {
  cin >> N >> M;
  // initialize
  int buf[M + 1];
  bool calling[N + 1];
  fill_n(buf, M + 1, 0);
  fill_n(calling, N + 1, false);
  
  // call dfs
  dfs(0, buf, calling);
}

 

백트래킹 예제 2 - 백준 9663번: N-queen

백트래킹 예제 하면 가장 유명한 문제가 아닐까 싶다.

 

9663번: N-Queen

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

노드의 유망성 판단 조건

• 현재 경로에 있는 모든 노드들이 공격하지 못하는 노드가 유망한 노드이다.
• 두 노드의 좌표가 각 (x1, y1) / (x2, y2)라 했을 때, 공격할 수 있다의 조건은 세 가지로 나눌 수 있다. 
  
  • x1 = x2 (직선)
  • y1 = y2 (직선)
  • |x2 - x1| = |y2 - y1| (대각선)

 

탐색 종료 조건

• 탐색한 경로 노드 수가 N이 되면 탐색을 종료한다.

이 문제를 풀 때, 좌표를 나타내기 위해 2차원 배열을 사용해도 된다. 그러나 1차원 배열을 사용하면 더욱 간단하게 풀 수 있다.

1차원 배열 board를 사용하여 저장

각 행마다 1개의 퀸을 놓아야 하는 상황이므로, 위의 그림처럼

 board[n]에 n번 행에 놓인 퀸의 열 번호를 저장하면 된다.

 

#include <iostream>
#define MAX 15

using namespace std;

int N;
int answer = 0;
int board[MAX] = {0,};

// 해당 노드가 유망한지 아닌지 판별하는 함수
bool promising(int row, int col) {
  for (int i = 0; i < row; i++) {
    if (board[i] == col || (row - i) == abs(board[i] - col)) return false;
  }
  return true;
}

void find_n_queen(int cnt) {
  // N개를 모두 선택했을 시 탐색을 종료한다. (경우의 수에 하나 추가)
  if (cnt == N) {
    answer++;
    return;
  }

  for (int i = 1; i <= N; i++) {
    // 노드가 유망한 경우, 즉 다른 퀸이 공격을 하지 못하는 위치인 경우 탐색을 진행.
    if (promising(cnt, i)) {
      board[cnt] = i;
      find_n_queen(cnt + 1);
    }
  }
}

int main() {
  cin >> N;
  find_n_queen(0);
  cout << answer << endl;
}