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

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

9663번: N-Queen

 

 

[ 문제풀이 ]

 

퀸의 특성을 이해하면 쉽게 풀 수 있는 문제입니다.

 

 

퀸은 가로 세로 대각선 방향의 모든 기물을 잡을 수 있습니다. 따라서 한 줄에는 하나의 퀸만 있을 수 있다는 점을 활용하여서 퀸을 놓을 때마다 좌표를 배열에 저장해줍니다.

 

재귀 호출을 할 때 퀸을 놓을 때마다 y값을 1씩 증가시킬 예정이므로 y값은 따로 저장하지 않습니다.

 

qx [15], up [30], down [30] 배열을 만들어 qx 배열에는 퀸의 x좌표를 up 배열에는 오른쪽 위 대각선 방향의 좌표, down 배열에는 오른쪽 아래 대각선 방향의 좌표를 각각 저장해줍니다.

 

또한 대각선 방향의 좌표들의 특성은 아래와 같기 때문에 up [y+x], down [y-x+N-1]을 각각 저장해 주어 퀸의 대각선 방향에 다른 퀸이 있는지 체크할 수 있습니다.

 

 

[ 소스 코드 ]

#include <iostream>
 
using namespace std;
 
int N;
int qx[15];        //퀸의 x좌표 저장
int up[30];        //퀸의 오른쪽 위 대각선 방향 체크
int down[30];    //퀸의 오른쪽 아래 대각선 방향 체크
int cnt;
int ans;
 
int check(int y, int x)    //y,x 좌표에 퀸을 놓을 수 있는지 체크하는 함수
{
    if (qx[x] || up[y + x] || down[y - x + N - 1]) {
        return 0;        //놓을 수 없다면 0 return
    }
 
    return 1;            //놓을 수 있다면 1 return
}
 
void dfs(int y)            //한 줄에 하나의 퀸만 들어갈 수 있으므로 
{                        //퀸을 놓으면 바로 y+1값으로 dfs 진행
    if (cnt == N) {
        ans++;
        return;
    }
    if (y >= N) {
        return;
    }
 
    for (int x = 0; x < N; x++) {
        if (check(y, x))
        {
            qx[x]++;        //x좌표 저장
            up[y + x]++;    //대각선 방향 저장
            down[y - x + N - 1]++;
            cnt++;
            dfs(y + 1);
            cnt--;
            qx[x]--;
            up[y + x]--;
            down[y - x + N - 1]--;
        }
    }
}
 
int main()
{
    cin >> N;
 
    dfs(0);
 
    cout << ans;
}