백트래킹(Backtracking)의 정의

• 백트래킹 또는 퇴각 검색이라고 부른다.
• 제약 조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략으로 특별한 알고리즘은 아니다.
• 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack하고 다른 후보군으로 넘어가서 계산량을 줄이는 기법이다.
• 실제 구현 시, 고려할 수 있는 모든 경우의 수를 상태공간트리(State Space Tree)로 표현한다.
  • 각 후보군을 DFS 방식으로 확인
  • 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
  • Promising : 해당 루트가 조건에 맞는지 검사하는 기법
  • Pruning(가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

    백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리에서 조건에 맞지 않는 노드는 더이상 DFS로 깊이 탐색을 하지 않고, 가지를 쳐버림(Pruning)

N Queen 문제 예제

풀이

• 한 행에는 반드시 하나의 퀸만이 존재할 수 있다.-> 퀸은 위, 아래, 왼, 오 대각선으로 모두 이동가능하기 때문이다.
• 트리 구조로 한 위치에서 퀸이 존재 할 수 있는지 여부를 확인하고 존재 할 수 없다면 아예 그 노드를 삭제하여 후보군을 모두 배제한다.
• DFS 방식으로 해결한다.

코드

#include <iostream>

using namespace std;

int queen_col[15] = {0};
int cnt = 0;

//현재 들어온 열 값이 가능한지 여부 판단
bool is_available(int current_row) {
	for (int row = 0; row < current_row; row++) {
		// 같은 열에 있어도 안되고, 대각선이 있어도 안된다.
		if ((queen_col[row] == queen_col[current_row]) || (current_row - row == abs(queen_col[current_row] - queen_col[row]))) {
			return false;
		}
	}
	return true;
}

void nqueen(int N, int current_row) {
	if (current_row == N) { //끝까지 다 놓은 경우 성공
		cnt++; //개수 +1
		return;
	}
	for (int col = 0; col < N; col++) {
		queen_col[current_row] = col; //현재 행에 후보 열을 놓아보고
		if (is_available(current_row)) {
			nqueen(N, current_row + 1); //가능하면 DFS
		}//안되면 후보 열 전체 탈락
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	nqueen(N, 0 );
	cout << cnt << '\n';

	return 0;
}