백준 C++ | #28 BOJ9663 N-Queen (백트래킹 알고리즘) C++ 문제 풀이

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

 

백트래킹 알고리즘을 복습해보자. 

 

백트래킹

백트래킹 알고리즘은 해를 찾는 도중에 해가 아니어서 막히면, 그 전으로 되돌아가서 다시 해를 찾는 기법을 말한다. 

DFS가 모든 경우의 수를 살핀다면, 백트래킹은 지금의 경로가 해가 아닌 것이 판명나면 다른 경로를 찾아간다. 

 

N-Queen

문제 설명은 간단하다. 

 

[문제]

N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 

 

[접근 방법]

각 행마다 퀸이 하나씩 존재하고, 각 열마다 퀸이 하나씩 존재한다. 

따라서 루프에서는 행이나 열을 기준으로 정해 1부터 N까지 증가시키며 퀸을 놓으면 된다. 

루프에서 i번째 행에 퀸을 놓을 차례라면, 1~i-1 행에서 이미 놓은 퀸과 비교하면서 퀸을 놓을 열을 결정하면 된다. 행이 N개, 열이 N개이므로, 이를 모두 판정하는데 O(N^2)이 걸린다.

 

block[i] := i번째 행에 놓인 퀸의 열 위치라고 하면, 

퀸을 놓을 열 j를 결정할 때

j == block[before] := 이전에 놓은 열과 이미 일치하거나

abs(j-block[before]) = = abs(i-before) := 대각선 경로에 있으면

j는 false

 

#include <iostream>

int N;
int* block = new int[16];
int cnt = 0;

void back(int depth) {
	if (depth == N) {
		cnt++;
		return;
	}
	for (int i = 0; i < N; i++) {
		bool flag = true;

		for (int j = 0; j < depth; j++) {
			if (block[j] == i || abs(depth - j) == abs(i - block[j])) {
				flag = false;
			}
		}
		if (flag) {
			block[depth] = i;
			back(depth + 1);
			block[depth] = 0;
		}
	} 
	return;
}

int main() {
	std::cin >> N;

	back(0);

	std::cout << cnt << std::endl;
	return 0;
}