백준 9663번: N-Queen

문제

문제 바로가기> 백준 9663번: N-Queen

풀이

NxN인 체스판 위애 퀸 N개를 서로 공격할 수 없게 놓는다는 말은 퀸이 놓였을 때 퀸을 기준으로 행(가로), 열(세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다는 말이다. 백트래킹을 이용하여 해당 자리에 퀸을 놓았을 때 유망한지 판단하는 방식으로 문제를 풀었다.

#include<iostream>
#define MAX_N 15
using namespace std;

int N, ans, board[MAX_N];

int promising(int r){ // 유망한지 판단
    for(int i=0; i<r; i++){
        if(board[r]==board[i] || r-i == abs(board[r]-board[i])) // 같은 열, 대각선에 있는 경우
            return 0;
    }
    return 1;
}

void backtracking(int r){
    if(r==N){
        ans++; 
        return;
    }
    for(int c=0; c<N; c++){
        board[r] = c; // r열 c행에 queen을 놓아봄
        if(promising(r)) // 유망한 경우
            backtracking(r+1); // 다음 행에 퀸을 놓아봄
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    backtracking(0);
    cout << ans;
}