[Python] 백준 9663 - N-Queen

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/9663

---

백트래킹 (backtracking)

참고 출처 | 파이썬으로 배우는 알고리즘 기초: 18. 백트래킹과 n-Queens 문제

백트래킹 = DFS + 가지치기

백트래킹은 모든 경우의 수를 다 조사하는 완전 탐색의 일종이다.

해답을 탐색하기 위한 탐색 공간을 상태 공간이라고 한다. 상태 공간을 트리 형태의 구조로 암묵적으로 해석한 것이 상태공간트리(state-space tree)다. 상태공간트리는 해를 찾기 위해 탐색해야 하는 모든 경로를 포함한다.

트리를 DFS로 탐색하는 과정에서, 현재 경로가 조건을 만족하는 해가 될 수 있는지를 판단한다. 이때, 해가 될 가능성이 있는 것을 유망하다(promising)고 한다. 현재 경로가 유망하지 않다면, 탐색을 중지하고 부모 노드로 되돌아간다. 이를 가지치기(pruning)라고 한다.

일반적인 백트래킹 알고리즘 (재귀로 구현)

void checknode (node v)
{
    node u;
    if (promising(v))
        if (v에 해답이 있으면)
        해답을 출력;
    else
        for (v의 모든 자식 노드 u에 대해서)
        checknode(u);
}

시간 초과 풀이

출처 | 파이썬으로 배우는 알고리즘 기초: 19. n-Queens 문제의 구현

위 영상의 코드를 거의 그대로 가져왔다.

파이참으로 돌려보니, n이 12만 되도 답을 구하는 데 10초 이상 걸렸다. (문제에서 n은 15 미만의 수다.) 백준에 제출하니 예상대로 시간 초과가 떴다.

나중에 직접 다시 구현해 볼 생각이다. 할 수 있을지는 모르겠지만...

from sys import stdin


def n_queens(i, col):
    global count
    n = len(col) - 1
    if promising(i, col):
        if i == n:
            count += 1
        else:
            for j in range(1, n + 1):
                col[i + 1] = j
                n_queens(i + 1, col)


def promising(i, col):
    k = 1
    flag = True
    while k < i and flag:
        if col[i] == col[k] or abs(col[i] - col[k]) == (i - k):
            flag = False
        k += 1
    return flag


n = int(stdin.readline())
col = [0] * (n + 1)
count = 0

n_queens(0, col)

print(count)