[백준/백트래킹/C++] 9663번 N-Queen

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

9663번: N-Queen

문제 해결 방법

백트래킹을 사용하여 풀수있다

퀸은 상, 하, 좌, 우, 대각선으로 움질일 수 있고 시간을 줄이기 위해 세가지 조건을 검사할 수 있다

우선 퀸이 좌우로 움질일 수 있기 때문에 한 행에는 하나의 퀸 만 놓을 수 있다는 것을 전제로 두고 시작한다

1번 조건 (상하로 움직일 수 있기 때문에 같은 열에 있는지 확인하는 조건) : i의 값이 같으면 continue 해준다

2번 조건 ( / 모양 대각선 위에 있는지 확인하는 조건) : k + i 값이 같으면 continue 해준다

3번 조건 ( \ 모양 대각선 위에 있는지 확인하는 조건) : k - i 값이 같으면 continue 해준다

#include <bits/stdc++.h>

using namespace std;

int n;
int result = 0;
bool isused1[40]; // column을 차지하고 있는지
bool isused2[40]; // / 뱡향 대각선을 차지하고 있는지
bool isused3[40]; // \ 방향 대각선을 차지하고 있는지

void backtrack(int k){
    if(k==n){
        result++;
        return;
    }
    for(int i=0; i<n; i++){ // (k, i)에 말을 놓으려고 할때
        if(isused1[i] || isused2[i+k] || isused3[k-i+n-1])
            continue;
        isused1[i] = 1;
        isused2[i+k] = 1;
        isused3[k-i+n-1] = 1;
        backtrack(k+1);
        isused1[i] = 0;
        isused2[i+k] = 0;
        isused3[k-i+n-1] = 0;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    backtrack(0);

    cout << result;

    return 0;
}

 

참고

https://www.youtube.com/watch?v=Enz2csssTCs&t=3s