[백준/BOJ] 9663번 N-Queen (C++)

www.acmicpc.net/problem/9663

9663번: N-Queen

전형적인 DFS + 백트래킹 문제

하나의 행에 퀸을 하나만 넣을 수 있으므로 열마다 퀸을 넣어보고 현재 위치를 기준으로 위, 왼쪽 위 대각선, 오른쪽 위 대각선을 검사합니다. 행이 n에 도달할 때 마다 하나의 경우의 수가 완성되므로 answer 값을 더해줍니다.

 

#include <iostream>
using namespace std;

int n,res;
bool map[15][15];

bool isPossible(int row, int col) {
    // 위 검사
    int x = row-1; int y = col;
    while(x>=0){
        if(map[x][y]) return false;
        x-=1;
    }
    // 왼쪽 위 대각선 검사
    x = row-1; y = col-1;
    while(x>=0 && y>=0){
        if(map[x][y]) return false;
        x-=1;
        y-=1;
    }
    // 오른쪽 위 대각선 검사
    x = row-1; y = col+1;
    while(x>=0 && y<n){
        if(map[x][y]) return false;
        x-=1;
        y+=1;
    }
    return true;
}

void DFS(int row) {
    if(row==n) { 
        res++;
    } else {
        // 한 행에는 하나의 Q만 올 수 있으므로 col만 for로 갱신
        for(int col=0;col<n;col++) {
            if(!map[row][col] && isPossible(row,col)) {
                map[row][col]=true;
                DFS(row+1);
                map[row][col]=false;
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    DFS(0); // 행 인덱스
    cout<<res;
}