문제

https://www.acmicpc.net/problem/9663

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

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

여기서 서로 공격할 수 없다는 조건은, 퀸의 일직선 및 대각선 상에는 아무것도 놓이면 안된다는 조건과 같다.

---

풀이

브루트포스

이 문제를 브루트포스로 풀면 시간복잡도가 O(N^2)이 된다.

더 효율적인 백트래킹을 이용해보자!

백트래킹

참고: https://chanhuiseok.github.io/posts/baek-1/

백트래킹의 가지치기로 문제를 풀면, 불필요한 재귀 호출을 수행하지 않기 때문에 훨씬 더 효율적으로 답을 구할 수 있다.

그리고 입력을 받을 때도 2차원이 아니라 1차원 배열로 입력을 받아야 시간초과가 발생하지 않는다.

(0, 2) (1, 0) (2, 3) (3, 1) 처럼 행과 열을 모두 저장하지 않고

(2, 0, 3, 1) 이렇게 퀸이 놓인 열의 위치만 저장해도 충분하다.

그 이유는 퀸의 열의 위치가 같다면 더 이상 재귀 호출을 하지 않고 그 다음 열로 넘어가기 때문이다.

그리고 위의 그림처럼 0행, 1행에는 퀸을 놓았고 이제 2행에 퀸을 놓으려고 하는 상황을 생각해보자. 0열에는 이미 퀸이 있기 때문에 1열로 넘어갈 것이다. 그 다음 위치인 (2, 1)은 (1, 0)과 대각선 상에 위치하기 때문에 넘어가야 한다. 대각선에 위치했다는 건 어떻게 검사할 수 있을까? 바로 현재 검사하고 있는 위치와 다른 퀸 사이의 행 번호 차이가 열 번호 차이와 같다면 대각선 상에 놓인 것이다. 따라서, 이 상황에서도 현재 탐색하고 있는 행의 위치와 1차원 배열에 저장된 열의 위치만 알면 된다.

그래서, 퀸이 놓이는 열의 위치만 1차원 배열에 저장하면 된다!

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

const int MAX = 16; 
int columns[MAX];
int N; 
int ans = 0;

bool promising(int row){
	for(int i = 0; i < row; i++){ 
		// 같은 열이나 대각선 상에 퀸이 놓여있으면 false 
		if(columns[row] == columns[i] || 
        	row - i == abs(columns[row] - columns[i])){
			return false; 
		}
	}
	return true; 
}

void dfs(int row){ 
	// N개의 행까지 온 경우, 가능한 경우의 수 증가 
	if(row == N){
		ans++; 
		return; 
	}

	for(int col = 0; col < N; col++){
    	// (row, col)에 체스를 놓아본다. 
		columns[row] = col; 

		// 유망하면 그 다음 행에 놓아본다. (깊이 우선 탐색) 
		// 그렇지 않으면 가지치기 (현재 행의 다음 열로 바로 이동) 
		if(promising(row)){ 
			dfs(row + 1); 
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin >> N;  

	dfs(0);

	cout << ans; 
	
	return 0; 
}