백준_9663_N-Queen (백트래킹)

📍백트래킹 개념

백트래킹은 브루트포스에 조건을 추가해서 절대 정답이 될리 없는 경우에서는 함수 호출을 중단하는 알고리즘이다.

즉, 브루트함수-재귀 패턴의 '다음 호출' 부분에서 무조건 다음 호출을 하는 브루트포스와 달리, 조건을 검사해서, 만족하면 다음 호출을 하는 방식이다.

 

📍N-Queen 문제 예시 코드

void calc(int row) {
	// 성공한 경우
	if (row == n) {
		ans += 1;
	}
    // 다음 호출
	for(int col=0; col<n; col++) {
		a[row][col] = true;
		if (check(row, col)) { // 이 부분이 백트래킹. 그냥 다음 호출을 하는 브루트포스와 달리 조건 검사.
			calc(row+1);
		}
		a[row][col] = false;
	}
}

 

📍문제 링크: https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

⭐📍위의 예시 코드에서 check함수는 현재의 row 이전의 모든 row에 대해서 열과 대각선을 검사하는 함수이다.

이렇게 풀 수도 있지만, 이 방법은 매 호출마다 이전의 모든 row를 검사하기 때문에 비효율적이다.

따라서, 열과 대각선을 기준으로 한 bool형 배열들을 만들어서 개선할 수 있다. 특정 열/대각선에 퀸이 1개라도 놓이면, 배열에 true를 넣어서, 이 배열값만을 검사하면, 검사 시간복잡도를 O(1)로 줄일 수 있다.

 

📍코드:

#include <iostream>
#include <cmath>

using namespace std;

int N;
bool board[15][15];
bool check_col[15], check_diag1[31], check_diag2[31]; // diag1: / , diag2: \

bool check(int row, int col) {
	if (check_col[col] == true) return false;
	if (check_diag1[row + col] == true) return false;
	if (check_diag2[row - col + N] == true) return false;
	return true;
}

int calc(int row) { // row 행에서 퀸을 어디에 놓을지 결정
	// 성공한 경우
	if (row == N) {
		return 1;
	}
	// 실패한 경우 코드 대신, '다음 호출'시 조건을 검사함. (같은 열, 대각선에 퀸이 있는 경우 다음 호출 X)
	// 다음 호출
	int ans = 0;
	for (int col = 0; col < N; col++) {
		if (check(row, col)) {
			check_col[col] = true;
			check_diag1[row + col] = true;
			check_diag2[row - col + N] = true;
			board[row][col] = true;

			ans += calc(row + 1);

			check_col[col] = false;
			check_diag1[row + col] = false;
			check_diag2[row - col + N] = false;
			board[row][col] = false;

		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	cout << calc(0) << '\n';
	return 0;
}