[백준] 9663번 N-Queen C++

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

C++

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

// nxn 체스판 위에 퀸 n개를 서로 공격할 수 없게 놓는 문제
// 퀸을 놓는 방법의 수
// 가로 세로 대각선에 있으며 안됨
// 그럼 백트래킹 방법

int chess[16];
int n,total = 0;

void search(int num) {
    if(num == n) {
        total++;
    }
    for(int i = 0; i < n; i++) {
        chess[num] = i;
        bool check = true;
        for(int j = 0; j < num; j++) {
            if(chess[num] == chess[j] || abs(chess[num] - chess[j]) == num - j) {
                // 같은 열인 경우에 안되고(한 가로에 있을때), 대각선일 때 안됨
                check = false;
                break;
            }
        }
        if(check) {
            search(num+1);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    search(0);
    cout << total << "\n";
}

문제풀이

• 퀸이 공격할 수 있는 경우는 같은 행이나 열에 있거나 대각선에 있는 경우다. N x N 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이므로 각 행에 퀸을 한 개씩 놓으려고 했다. 그러면 같은 열과 대각선에 있는지 파악하면 되기 때문에 백트래킹을 사용했다. search 함수의 매개변수 num은 행을 의미하고, i는 열을 의미한다. 각 행에 모든 열을 비교하면서 조건에 맞을 경우 다음 행으로 넘어간다. 마지막 행까지 가면 total++해주고 모든 경우의 수를 파악한 뒤 total을 출력한다.

Comment

• 다른건 크게 어렵지 않았는데 같은 대각선에 있는거를 어떻게 파악할 수 있을지에 대해서 계속 고민했던 것 같다. 같은 대각선에 위에 있다는건 행 차이와 열 차이가 같다는 것이다. 이걸 찾는데 꽤 많은 시간이 걸렸다는,,,