(골드 4)백준 9663: N-queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

핵심

N × N인 2차원 배열 위에 상하, 좌우, 대각선 상에 겹치는 않는 지점 N개를 놓을 수 있는 경우의 수.

---

내가 작성한 코드

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int n;
int table[15][15];
int result = 0;

void dfs(int j, int cnt)
{
    if (cnt == n)
    {
        result++;
        return;
    }

    if (j == n)
    {
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (table[j][i] == 0)
        {
            // cout << j << i << "\n";
            // 수직 체크
            for (int k = j; k < n; k++)
            {
                table[k][i]++;
            }
            // 대각선 마킹
            for (int k = 1; j + k < n && i + k < n; k++)
            {
                table[j + k][i + k]++;
            }
            for (int k = 1; j + k < n && i - k >= 0; k++)
            {
                table[j + k][i - k]++;
            }
            dfs(j + 1, cnt + 1);
            // 수직 마킹
            for (int k = j; k < n; k++)
            {
                table[k][i]--;
            }
            // 대각선 마킹
            for (int k = 1; j + k < n && i + k < n; k++)
            {
                table[j + k][i + k]--;
            }
            for (int k = 1; j + k < n && i - k >= 0; k++)
            {
                table[j + k][i - k]--;
            }
        }
    }

    return;
}

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

    cin >> n;

    dfs(0, 0);

    cout << result;

    return 0;
}

---

풀이

아주 클래식한 문제다.

나는 하나의 행에는 반드시 하나의 퀸을 놓아야 한다는 접근방식으로 back tracking을 구현했다.

 

1. n을 입력받는다.

2. 0번행의 (0,0) 부터 퀸을 놓고 그 아랫행들에 퀸을 놓을 수 없음을 마킹한다.

3-1. 다음행에 가능한 위치에 퀸을 놓고 2, 3을 반복한다.

3-2. 퀸을 놓을 수 없으면 돌아간다.

4. 퀸이 n개 놓여지면 카운트하고 돌아간다.