[BOJ / C++] #9663 N-Queen

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

문제풀이

전형적인 백트래킹 문제이다.

• dfs 함수 : 행 값을 인자로 받고, i=0부터 N-1까지 돌면서 현재 행의 i열에 퀸을 놓을 수 있는지 확인하면서 (promising) dfs를 진행해준다.
  따라서 main에서 0행부터 시작하며 N행까지 왔을 때 return한다.
• promising 함수 : 행과 열값을 인자로 받는다.

1. 위쪽 확인 : 이전 행에 현재 열 값이 있는지
2. 위쪽 대각선 확인 : 이전 행과 현재 행값의 차이 == 이전 열과 현재 열값의 차이 일 때 퀸이 대각선에 존재한다.

• board 1차원 배열의 인덱스는 각 행으로, 퀸이 놓인 곳의 열 값을 값으로 가진다.

#include <iostream>
#include <cstring>
using namespace std;

int N;
int board[15]; //각 행에 어떤 열에 퀸이 놓인지.
int res;

bool promising(int r, int c){
    for(int i=0;i<r;i++){
        if(board[i]==c||abs(c-board[i])==r-i)return false; //위쪽 행 또는 대각선에 있을 경우}

    }
    return true;
}

void dfs(int row){
    if(row==N){
        res++;
        return;
    }
    //모든 열을 본ㄷㅏ
    for(int i=0;i<N;i++){
        if(promising(row,i)){ //row행 i열에 놓을 수 있는지
            board[row]=i;
            dfs(row+1); //놓았으면 다음행 봄
            board[row]=-1;
        }
    }
}

int main(){
    memset(board,-1,sizeof(board)); //어떤 열에 놓을지 들어가므로, 0 이상의 수는 안 됨!
    cin>>N;
    dfs(0); //0행부터 시작.
    cout<<res<<"\n";
}