(C++) 백준 9663번 - N-Queen

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

9663번: N-Queen

풀이

백트래킹을 활용하여 풀이하였다.

Queen은 같은 행이나 열, 같은 대각선 상에 존재하면 서로를 잡을 수 있다는 점을 알아야 한다.

그렇기에 한 행에 놓으면 같은 행의 다른 칸에 놓을 수 없음을 이용하여 한 행에 Queen을 하나씩만 두고, 열과 대각선 상만 피해서 Queen을 놓게 구현하면 된다.

#include <iostream>

using namespace std;

int n;
int isUsedcol[15]; // 이미 들어간 행에 체크
int isUseddiagu[30]; // 이미 들어간 우측 상단으로 향하는 대각선에 체크
int isUseddiagl[30]; // 이미 들어간 우측 하단으로 향하는 대각선에 체크
int cnt;

void nq(int queen){
    if(queen == n) { // base condition
        cnt++;
        return;
    }
    for(int i = 0; i < n; i++){
    	// 잡을 수 있는 위치에 이미 존재한다면 skip
        if(isUsedcol[i] or isUseddiagu[i+queen] or isUseddiagl[queen-i+n-1]) continue;
        isUsedcol[i] = 1;
        isUseddiagu[i+queen] = 1;
        isUseddiagl[queen-i+n-1] = 1;
        nq(queen+1);
        isUsedcol[i] = 0;
        isUseddiagu[i+queen] = 0;
        isUseddiagl[queen-i+n-1] = 0;
    }
    
}

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

    cin >> n;
    nq(0);
    cout << cnt;
}

힌트(라고할뻔~)