[Gold 4] 9663 N-Queen

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

 

이 문제는 백트레킹을 사용하면 해결할 수 있다.

 

백트레킹을 사용하는 이유는 다음과 같다.

1. 한개의 줄에 퀸을 배치하기 위해서는 대각과 위를 비교해야한다.

2. 만약 대각 성분이나 위를 비교했을 때 충돌할 경우 이전 행으로 이동해서 다른 위치에 퀸을 배치해야함

 

이 문제의 백트레킹을 사용하는 이유를 살펴보면 각 행에는 퀸이 1개만 존재한다는 것을 알 수 있다.

따라서 col 배열을 통해 각 행에 위치한 퀸의 위치를 저장한다.

- 퀸이 (0, 3)에 위치한다면 col[0] = 3 

 

퀸을 배치하고, 배치한 퀸이 충돌하는지 검사하는 방법

1. col[0] = 1, col[1] = 1, col[2] = 1인 경우는 col[x]의 값이 일치하여 충돌하는 것을 알 수 있다.

2. col[0] = 1, col[1] = 2 인 경우는 col[x] - col[j] 의 값이 같을 경우 

-> 즉, x - j의 차이 값이 배치 값의 차이가 같을 경우 대각 성분이 일치한다고 알 수 있다.

 

위에서 구한 검사 방법은 하나의 퀸을 배치할 때 이전에 배치한 퀸의 모든 위치를 검사해야한다.

따라서 queen을 배치할 열인 x가 주어질 때 0의 위치에서 x의 위치까지 모두 검사하여 충돌하는지 검사한다.

이후, 모든 위치를 검사한 후 충돌하지 않는다면 다음 위치에 퀸을 배치할 수 있는지 확인한다.

 

모든 위치에 퀸을 배치하였다면, 정답 수를 1증가시킨다. 

 

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

int N;
int answer;
int col[15];
void nqueen(int x){
    if(N == x)
        answer++;
    else{
        for(int i = 0;i<N;i++){
            col[x] = i;
            bool isCollision = false;

            for(int j = 0;j<x;j++){
                if(col[x] == col[j] || abs(col[x] - col[j]) == x - j){
                    isCollision = true;
                    break;
                }
            }
            if(!isCollision)
                nqueen(x + 1);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;

    nqueen(0);
    cout<<answer;
}