[백준 9663] N-Queen - C++ / 백트래킹 알고리즘

문제

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

9663번: N-Queen

나의 코드

#include <iostream>
#include <vector>
#define MAX 15
 
using namespace std;
 
vector<bool> visited1(MAX);
vector<bool> visited2(MAX + MAX);
vector<bool> visited3(MAX + MAX);
int result, n;
 
void Queen(int x) {
    if (x == n) {
        result++;
        return;
    }
    for (int y = 0; y < n; y++) {
        if (visited1[y] || visited2[x + y] || visited3[x - y + n - 1]) continue;
        visited1[y] = true;
        visited2[x + y] = true;
        visited3[x - y + n - 1] = true;
 
        Queen(x + 1);
        visited1[y] = false;
        visited2[x + y] = false;
        visited3[x - y + n - 1] = false;
    }
}
 
int main(void) {
    cin >> n;
 
    result = 0;
 
    Queen(0);
 
    cout << result << '\n';
}
 

가로(->)가 X, 세로가 Y라고 했을 때,

같은 X축 QUEEN은 존재할 수 없으므로 X+1로 넘어간다.

마지막 X = N - 1에 왔을 때 RESULT++로 하고 이전 상태로 돌아간다.

이전 상태로 돌아가면서 Y++이 실행되고 또다른 경우의 수를 탐색한다.

백트래킹은 DFS을 기본적으로 사용한다는 사실을 알 수 있다.

Q
	Q
				Q

 

채스 퀸에 대해서 몰랐는데 가로,세로, 대각선에 있으면 공격을 할 수 있다.

따라서 각 visited를 구현했는데, 일일이 하나씩 다 탐색하면 시간초과문제가 발생하므로

가로 visited1, 오른쪽 위로 가는 대각선 visited2, 오른쪽 아래로 내려가는 대각선 visited3로 나눠서 탐색하면 된다.

 

 

이러한 아이디어는 참고했다 -> https://blog.encrypted.gg/732?category=773649