BOJ 9663 · N-Queen

알고리즘 분류 : 백트래킹  

N-퀸은 백트래킹 알고리즘에서 가장 대표적인 문제다. N x N 사이즈의 체스판에 N개의 퀸을 놓는 방법의 수를 구해야 한다.

다음 위치에 퀸을 놓을 때마다, 해당 위치에 퀸을 놓을 수 있는지 확인하면서 백트래킹을 하면 된다.

• 가능 여부를 확인할 때, 하나의 배열에서 매번 상하좌우 대각선을 확인하는 것은 효율적이지 않다.
• 3개의 배열을 만들고, 각각 세로 줄(|), 대각선 줄(/), 대각선 줄(\)을 체크한다.
• N x N 판에서 한 칸의 인덱스를 [X, Y]라 하자. 세로 줄(|)은 각 칸이 [Y]이며, 대각선(/)은 각 칸이 [X+Y]이고, 대각선(\)은 각 칸이 [X-Y+N-1]이다. 아래의 그림은 N이 5일 때의 예시다.
• solve 함수에서 인자 i는 행(row)이며, for 문의 j는 열(column)을 나타낸다. 즉, 가장 위 행에서 아래 행으로 순서대로 내려가면서, for 문과 if 문을 통해 어떤 열에 놓을지 결정하는 것이다.

---

C++ 소스코드

#include <cstdio>

int n, ans;
bool a[14], b[27], c[27];

void solve(int i) {
    if (i == n) {
        ans++;
        return;
    }
    for (int j=0; j<n; j++) {
        if (a[j] || b[i+j] || c[i-j+n-1]) continue;
        a[j] = b[i+j] = c[i-j+n-1] = true;
        solve(i+1);
        a[j] = b[i+j] = c[i-j+n-1] = false;
    }
}

int main() {
    scanf("%d", &n);
    solve(0);
    printf("%d\n", ans);
    return 0;
}

---

PyPy3 소스코드

n, ans = int(input()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve(i):
    global ans
    if i == n:
        ans += 1
        return
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False

solve(0)
print(ans)

✓ Python 3로 제출하면 시간 초과가 나오므로, PyPy3로 제출해야 한다.

✓ 편법으로 아래와 같이 해결할 수도 있다. N이 15 미만이므로, 값을 모두 미리 구해서 출력만 하면 된다.

a = (0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596)
print(a[int(input())])

---

참고

• 백준 온라인 저지 : BOJ 9663