[9663번] N-Queen

이 문제는 NxN 체스판에 퀸 N개를 서로 공격하지 못하는 위치에 놓는 경우의 수를 구하는 문제입니다. 퀸은 체스판 위에서 상하좌우 대각선으로 공격할 수 있는 기물인 것을 유의해야합니다.

단 문제의 N은 14이하이므로 백트래킹을 이용해서 문제를 풀 수 있습니다.

이 문제에서 가장 어려운 부분은 특정 좌표에 퀸을 둘 수 있는지 어떤 식으로 판별하는가 입니다.

저희가 실제 코딩 할 때 2차원 배열의 좌표를 쓰는 것이 편하기 때문에 좌표로 생각을 하겠습니다.

퀸이 놓인 자리에는 행과 열이 같은 자리에는 다른 퀸을 못놓으며, 좌측 하단과 우측 상단을 잇는 대각선은 x가 1 증가하면서 y가 1감소하는 대각선입니다. 그리고 좌측 상단과 우측 하단을 잇는 대각선은 x-y가 같은지 보면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
bool isused1[40]; //column을 차지하고 있는지
bool isused2[40]; // /방향 대각선을 차지하고 있는지
bool isused3[40]; // \방향 대각선을 차지하고 있는지

int cnt = 0;
int n;
void func(int cur) { //cur번째 row에 말을 배치할 예정임)
	if (cur == n){ //N개를 놓는데 성공했다면
    	cnt++;
        return;
    }
    for (int i = 0; i<n ; i++) { //(cur, i)에 퀸을 놓을 예정
    	if (isused1[i] || isused2[i+cur] || isused3[cur-i+n-1]) //column이나 대각선 중에 문제가 있다면
        	continue;
        isused1[i] = 1;
        isused2[i+cur] = 1;
        isused3[cur-i+n-1] = 1;
        func(cur+1);
        isused1[i] = 0;
        isused2[i+cur] = 0;
        isused3[cur-i+n-1] = 0;
    }
}
int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    func(0);
    cout << cnt;
}

코드의 흐름에서보다는 20~22번째 줄의 처리와 같이 함수를 들어갔다가 나올 때 isused 값들을 false로 만들어줘야 하는걸 꼭 까먹으면 안됩니다.

 

※A1에 퀸을 놓는다면 B1,B2에 퀸을 놓는 경우는 해볼 필요가 없어지는 것과 같은 상황을 백트래킹에서는 가지치기라고 부르는데 가지치기가 빈번하면 백트래킹의 시간복잡도를 가늠하기가 힘듭니다. 그렇기 때문에 문제를 보고 시간복잡도가 가늠이 잘 안가는데 N이 많이 작아 백트래킹으로 푸는 문제일 것 같다는 생각이 들면 직접 구현한 뒤 가장 시간이 오래 걸릴만한 케이스를 직접 돌려봐서 시간 초과가 나는지 안나는지를 보면 됩니다. 

위와 같은 문제는 N=14를 넣어보고 시간이 애매하면 최적화를 시킨 후에 제출하면 됩니다. 시간을 로컬에서 측정시에는 반드시 Release 모드로 실행을 해야하고 보통은 서버가 로컬보다 빠르다는 점도 기억하는게 좋습니다.