[백트랙킹]백준9663번 N-Queen

백준9663

백트랙킹을 적용할 수 있는 유명한 문제이다.

N*N 체스판에 퀸 N 개를 서로 공격하지 못하는 위치에 놓는 경우의 수를 찾는 문제이다.

Queen은 상하좌우 + 대각선 공격이 가능하다.

우선, Queen은 자신이 속한 행, 렬, 대각선 방향으로 칸 수 제한 없이 공격이 가능하다.

따라서, Queen은 한 행에 하나밖에 존재하지 못한다.

위에서부터 가능한 위치에 Queen을 하나씩 두면서 내려오고, N번째 행에 queen을 두었다면 N 개의 Queen을 두는 것을 성공한 것으로 한다.

특정 좌표가 Queen을 놓기에 적절한 자리인지 확인하기 위해서는 해당 좌표의 같은 행, 열, 대각선 두 방향에 Queen이 있는지 확인해야 한다.

하나의 좌표마다 반복문을 통해 탐색해도 되지만, Queen을 배치할 때 잘 기록을 해두면 백트랙킹을 사용해 간단하게 구현이 가능하다.

그 전에, 간단한 수학적인 지식이 필요하다.

우선 하나의 행씩 내려가며 Queen을 배치한다고 하였기 때문에 행(좌,우) 는 확인하지 않아도 된다.

열은, 자신과 일치하는 y 좌표를 가진 Queen이 있는지 확인하면 된다.

두 방향의 대각선이 문제인데,

• 우상향 대각선 : x+y가 같으면 같은 우상향 대각선 상에 있는 것으로 볼 수 있다.
• 좌상향 대각선 : x-y가 같으면 같은 좌상향 대각선 상에 있는 것으로 볼 수 있다.

따라서, 만약 4*4 체스판에서 (1,2) 좌표에 Queen이 있을 때, (3,0) 좌표에 Queen을 놓을 수 있는지의 여부는 x+y값이 같은지의 여부로 확인할 수 있다.

이를 위해 체스판 위에서 만들어질 수 있는 모든 대각선과 열들을 배열로 만들어 관리할 필요가 있다.

1. 첫 번째는 같은 열인지를 확인할 배열이다. 이 배열의 크기는 N 이다 (N 개의 열이 있기 때문에)
2. 두 번째는 같은 우상향 대각선 상에 있는 지를 확인할 배열이다. 이 배열의 크기는 (1 + 2 * (N-1)) 이다.
3. 세 번째는 같은 좌상향 대각선 상에 있는지를 확인할 배열이다. 이 배열의 크기는 (1 + 2 * (N-1)) 이다.

4*4 체스판에서 가능한 대각선들과 열들을 표시해보면

다음과 같다.

하나의 퀸을 배치했을 때 자신과 같은 열, 자신이 속한 좌상향, 우상향 대각선들을 선택하지 못하게 전부 막아버리는 것과 같다.

#include <iostream>

using namespace std;

bool arr1[15]; // 같은 열인지를 확인할 배열. 문제의 조건이 1~14까지라 15로 두었다. 
bool arr2[29]; // 15 * 15의 체스판일 때 가능한 대각선은 29개라 29로 두었다. 
bool arr3[29]; // 15 * 15의 체스판일 때 가능한 대각선은 29개라 29로 두었다. 
int N;
int cnt = 0;   // 정답 

void btk(int n){ // 자신이 몇 번째 행에 있는지를 나타내는 n 
    if(n==N){    // 만약 n 이 N 과 같다면 끝 행에 있는 것이기 때문에 완료한 것이다.base condition
        cnt++;   // Queen 배치가 가능한 경우의 수 1 증가.
        return;
    }
    for(int i=0;i<N;i++){ // 열을 확인할 반복문이다. 
        int y = n; // 현재의 y 좌표는 자신이 몇 번째 행에 와있는지와 같다. 따라서 n.
        int x = i; // 현재의 x 좌표는 자신이 0에서 시작해 몇 번째 열에 속해있는지와 같다. 따라서 i
        if(!arr1[x] && !arr2[x+y] && !arr3[x-y+N-1]){ // 상하, 좌대각선 우대각선 모두 가능
            arr1[x] = true;    // 현재 내가 속한 열은 이제 아무도 못 놓는다.
            arr2[x+y] = true;  // 현재 내가 속한 우상향 대각선에는 이제 아무도 못 놓는다.
            arr3[x-y+N-1] = true; // 현재 내가 속한 좌상향 대각선에는 이제 아무도 못 놓는다.
            btk(n+1); // Queen을 놓았으니 이 자리에 놓았을 때 밑의 행에서 가능한 자리를 찾는다.
						// 내가 현재 행에서 Queen을 놓았을 경우에 밑에 행에서 가능한 모든 경우의 수를 확인함.
						// 방금 놓은 자리 말고 현재 행에서 다른 자리를 확인해야 하기 때문에 다시 물러야 함.
            arr1[x] = false; 
            arr2[x+y] = false;
            arr3[x-y+N-1] = false;
        }
    }
}

int main(){

    cin >> N;
    
    btk(0); //시작은 0번 째 행에서. 
    cout << cnt;
}