[백준 / BOJ] 9663 N-Queen

알고리즘 분류: 백트래킹

문제 링크: www.acmicpc.net/problem/9663

9663번: N-Queen

• 먼저, 한 행에 한 개의 퀸만 놓는 방식으로 진행하면 가로 방향은 체크할 필요가 없다.
• 그렇기 때문에 세로, 슬래시, 역슬래시 방향으로 방문 확인을 해줄 배열을 3개 만들어서 해결했다.
• 재귀를 돌며 x+1이 되므로 행이 한 칸씩 내려가고 방문확인을 통해 퀸을 놓을 수 있는 좌표인지 확인한다.
• 놓을 수 있는 곳이면 정답을 +1 하는 방식으로 백트래킹이 진행된다.

예를 들어 n=3일 때를 표로 그려보면 다음과 같다.

1. y: 세로 방향

0	1	2
0	1	2
0	1	2

2. x+y: 슬래시 방향

0	1	2
1	2	3
2	3	4

3. n-1+x-y: 역 슬래시 방향

2	1	0
3	2	1
4	3	2

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

#define ll long long
#define INF 1e9

using namespace std;

//https://www.acmicpc.net/problem/9663 N-Queen

int visit1[20]; //y
int visit2[30]; //x+y
int visit3[30]; //n-1+x-y
int n;
int ans;

void go(int x) {
    if(x == n) {
        ans++;
        return;
    }
    for(int y=0; y<n; y++) {
        if(visit1[y] || visit2[x+y] || visit3[n-1+x-y]) continue;
        visit1[y] = visit2[x+y] = visit3[n-1+x-y] = 1;
        go(x+1);
        visit1[y] = visit2[x+y] = visit3[n-1+x-y] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    go(0);
    cout << ans;
    
    return 0;
}