# 백준 : N-Queen (9663)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_9663_N-Queen)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

bool moveup[30];
bool movedown[30];
bool thisrow[15];
int N;
int cnt;

void DFS(int row) {
    if(row >= N)    cnt++;
    for(int i=0; i<N; i++) {
        if((!thisrow[i]) && (!moveup[row + i] && !movedown[N - 1 + (row - i)])) {
            thisrow[i] = moveup[row + i] = movedown[N - 1 + (row - i)] = true;
            DFS(row + 1);
            thisrow[i] = moveup[row + i] = movedown[N - 1 + (row - i)] = false;
        }
    }
}

int main(void)
{
    cin>>N;
    DFS(0);
    cout<<cnt<<endl;
    return 0;
}

풀이

솔직히 이 문제 굉장히 어려웠다. 사실 아직도 정확하게 이해하지 못하고 있는 것 같기도..
(다시 재 풀이해보겠다. 우선 지금까지 이해한 부분을 토대로 작성해보면)

처음 내가 풀이한 방식(실제로 해결하지 못한)은 
1. 체스 맵을 2차원으로 완벽하게 만든 후
2. [0,0]에서부터 [1,0], [2,0] 순으로 차례차례 내려가서 [N-1,0]까지 합산하고
3. 각 경우에 맞게 [y,x+1]을 기준으로 대각선, 바로 옆을 제외한 모든 부분을 DFS
였는데. 실제 한글로 적었어도 이해하기 어려울정도이지만. 
물론 풀이조차 이해하지 못할정도로 꼬여서 포기.

그러던 중 
1. 어차피 한 줄에는 하나씩밖에 못가니까 1차원으로 해결해보자
2. 그리고나서 대각선을 하나씩 확인해보면 되겠다

식으로 진행했지만 이 또한 실패 (대각선에서 너무 많은 고민거리가 생겼었다)
결국 구글을 참조해서 어떻게 다른 분들은 이 문제를 해결했는가 확인해보았는데.
굉장히 간단하게 풀었다. (그래서 이 문제의 정답률이 60%에 육박하는구나)

1. 각 row에 체스 말이 있는지 여부를 판단하는 1차원 배열 1개
2. 해당 체스 말을 기준으로 대각선 아래부분에 다른 체스말이 있는지 판단하는 1차원배열 1개
2.1. 대각선 아래라는 의미는 [0,0], [1,1], [2,2] 순의 오른쪽 아랫방향
3. 해당 체스 말을 기준으로 대각선 윗 부분에 다른 체스말이 있는지 판단하는 1차원배열 1개
3.1. 대각선 위라는 말은 [4,0], [3,1], [2,2] 순의 오른쪽 윗방향

체스말은 오직 [0,0], [1,0], [2,0] 순으로만 이동하면서
위의 1차원 배열에 주변에 있는 녀석들이 유무만 체크해준다 (굉장히 신박한 방법)

각 1차원 배열들은 N개 기준으로 2N-1개의 갯수만큼의 대각선이 존재한다.
1. 대각선 아래부분은 [y,x]일 때 N - 1 + y-x가 모두 일치
2. 대각선 윗부분은 [y,x]일 때 y+x가 모두 일치

이러한 계산방법으로 퀸의 움직일 수 있는 예상 범위를 모두 체크해주고
마지막에 백트래킹을 할 수 있도록 예상 범위를 다시 제거해주면 된다.

결론은? 다시 풀어보자.