[백준 9663번] N-Queen

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

9663번: N-Queen

풀이) 

각 좌표에 퀸을 놓을 수 있는지 확인만 해주면 된다. 열은 확인할 필요가 없고, 위랑 왼쪽대각선, 우측대각선만 확인을 해주면 된다. 해당 자리에 값을 넣을 수 있다면, 방문처리를 해놓고 dfs를 이어나가면 되고, 끝나면 다시 방문처리를 false로 원래대로 돌려놓으면 된다.

#include <iostream>
using namespace std;

int N, ans = 0;
int map[16][16];

int positionCheck(int x, int y)
{
    int i;
    int j;

    i = x;
    j = y;
    while (i >= 0)
        if (map[i--][y])
            return (0);

    i = x;
    j = y;
    while (i >= 0 && j >= 0)
        if (map[i--][j--])
            return (0);

    i = x;
    j = y;
    while (i >= 0 && j < N)
        if (map[i--][j++])
            return (0);
    return (1);
}

void dfs(int idx)
{
    if (idx == N)
    {
        ans++;
        return ;
    }
    for (int i = 0; i < N; i++)
    {
        if (positionCheck(idx, i))
        {
            map[idx][i] = 1;
            dfs(idx + 1);
            map[idx][i] = 0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N;
    dfs(0);
    cout << ans;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!