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

백준의 N-Queen(9663) 문제이다.

( 문제 바로가기 )

백트래킹의 가장 대표적인 문제 N-Queen이다.

[ 문제풀이 ]

1) 먼저 퀸은 가로, 세로, 대각선으로 나아갈 수 있는 말이다. 즉, 퀸 하나를 놓았을 때, 그 퀸과 같은 가로줄 혹은 세로줄, 혹은

   대각선줄에는 또 다른 퀸이 놓여질 수 없음을 의미한다.

2) 본인은 DFS의 재귀호출을 통해서 문제를 해결하였다. 퀸을 놓을 자리를 설정해주고, 만일 그 자리가 놓을 수 있는 위치라면

   재귀를 통해서 그 다음 말을 놓는 식으로 진행하였다.

   먼저 맵을 관리하기 위해서 1차원 배열 MAP[]을 사용하였다. 맵을 관리하면서도 2차원 배열을 사용하지 않은 이유는

   굳이 맵 좌표 하나하나를 설정해 가면서 체크를 해줄 필요까지는 없기 때문이다.

   사실, 같은 라인에 있는지 혹은 같은 대각선에 있는지만 판단을 해주면 되기 때문이다.

   즉, 최대 15라인까지 주어지는 맵에서, 예를들어서 첫 번째 퀸이 1번 라인에 놓여졌으면, 두 번째 퀸은 1번 라인에

   놓여질 수 없다고 계산을 해버리면 되는 것이다.

  

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define endl "\n"
#define MAX 15
using namespace std;
 
int N, Answer;
int MAP[MAX];
 
void Input()
{
    cin >> N;
}
 
bool Can_Pos(int line)
{
    for (int i = 0; i < line; i++)
    {
        if (MAP[i] == MAP[line] || abs(MAP[line] - MAP[i]) == line - i) return false;
    }
    return true;
}
 
void DFS(int line)
{
    if (line == N)
    {
        Answer++;
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        MAP[line] = i;
        if (Can_Pos(line) == true) DFS(line + 1);
    }
}
 
void Solution()
{
    DFS(0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}