[백준] 9663 N-Queen c++

1. 문제

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

2. 풀이

BackTracking 알고리즘을 사용한다

<생각해야 하는 조건>

1. 퀸이 공격할 수 있는 방향을 체크해야 한다.

퀸이 갈 수 있는 방향

1. 같은 행
2. 같은 열
3. (왼쪽 ->오른쪽 기준) 올라가는 대각선
4. (왼쪽 ->오른쪽 기준) 내려가는 대각선
   이와 같은 방향으로 퀸이 갈 수 있으므로 배열을 사용해 퀸이 갈 수 없는 곳을 체크해 놓는다.

1. 같은 행
   같은 행에 하나씩 놓는다고 가정하므로 1번 조건은 확인하지 않는다.

2. 같은 열
   used1[]은 열을 체크함으로써 같은 열에 퀸을 놓을 수 없도록 한다.

3. (왼쪽->오른쪽 기준) 올라가는 대각선

위의 그림을 살펴보면 올라가는 대각선이 지나는 칸의 행렬을 더한 값은 항상 같다

0+3 = 1+2 = 2+1 = 3+0 = 3

따라서 used2[]를 사용해 row+col 이 같은 경우에는 퀸을 놓을 수 없다고 가정한다.

4. (왼쪽 오른쪽 기준) 내려가는 대각선

위의 그림을 살펴보면 내려가는 대각선을 지나는 칸의 행,령을 뺀 값은 항상 같다.

0-1 = 1-2 = 2-3 = 3-4 = 4-5 = -1

따라서 used3[]을 사용해 row-col 이 같은 경우에 퀸을 놓을 수 없다고 가정한다.
그러나 row-col이 음수가 나오는 경우가 있으므로 row-col +(n-1) 을 해준다.

위의 조건에 해당하지 않을 경우 퀸을 놓고 BackTracking함수를 반복한다.

2. 놓은 퀸의 개수가 N개 임을 확인해야 한다.

퀸의 개수가 N일 때의 경우의 수를 출력한다.

<위의 조건을 사용하여 BackTracking 함수를 작성한다.>

void BackTracking(int row) {
    if (row == n) {
        answer++;
        return;
    }
    for (int col = 0; col < n; col++)
    {
        if (used1[col] || used2[col + row] || used3[row - col + n - 1])
            continue;
        used1[col] = true;
        used2[col + row] = true;
        used3[row - col + n - 1] = true;
        BackTracking(row + 1);
        used1[col] = false;
        used2[row+col] = false;
        used3[row - col + n - 1] = false;
    }
}

3. 전체 코드

#include <iostream>

using namespace std;

int n, answer = 0;

bool used1[40],used2[40],used3[40];
//used1 : 같은 행에서 열 중복 확인
//used2 :(왼->오 기준)내려가는 대각선 확인
//used3 : (왼->오 기준)올라가는 대각선 확인

void BackTracking(int row) {
    if (row == n) {
        answer++;
        return;
    }
    for (int col = 0; col < n; col++)
    {
        if (used1[col] || used2[col + row] || used3[row - col + n - 1])
            continue;
        used1[col] = true;
        used2[col + row] = true;
        used3[row - col + n - 1] = true;
        BackTracking(row + 1);
        used1[col] = false;
        used2[row+col] = false;
        used3[row - col + n - 1] = false;
    }
}


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

    cin >> n;
    BackTracking(0);
    cout << answer;

    return 0;
}