[백준] 9663 - N-Queen

백트래킹 문제의 대표적인 유형인 N-Queens 문제이다.

n = 4인 경우를 가정하고 문제를 풀어보면,

다음과 같은 체스판이 있을 때, 각 행 번호를 인덱스로 갖는 col 배열을 생각해볼 수 있다.

col = [0, 0, 0, 0]

즉, col[i] = j 이면 i번째 행의 j번째 열에 퀸이 있다는 뜻이다.

0번째 행부터 3번째 행까지 위에서부터 순서대로 퀸을 놓아야 하는데 (탐색) 이 때, 현재 놓으려고 하는 퀸이 이전에 이미 놓은 퀸에 의해서 잡힐 위치인지 확인하고 (조건 확인) 잡힐 위치라면 탐색을 멈추고 (가지치기) 이전 단계로 돌아가서 새로운 위치에 퀸을 놓는다. (백트래킹)

0번째 행의 1번째 열에 퀸 놓기, col[0] = 1

두번째 퀸을 1번째 행의 2번째 열에 놓았으나 첫번쨰 퀸에 의해서 잡히므로 다시 빼기

두번째 퀸을 1번째 행의 3번째 열에 놓고 확인해봤을 때에 잡힐만한 퀸이 없으므로 확정하고 3번째 퀸 놓기

이와 같은 과정을 반복하여 4개의 퀸을 놓을 수 있는 모든 경우의 수를 찾는다.

코드는 다음과 같다.

 

# 백트래킹을 진행하는 함수
def n_queens(x):
    global n, count

    # n개의 모든 퀸을 다 잘 놓았을 경우, count를 1만큼 증가
    if(x == n):
        count += 1
        return

    # 열의 개수만큼 for문을 돌면서 퀸을 놓아본다음 이전에 놓은 퀸에 의해서
    # 잡히지 않는다면 확정하고 다음 퀸 놓기
    for i in range(n):
        col[x] = i
        if(promising(x)):
            n_queens(x + 1)

# 놓은 퀸이 이전에 놓은 퀸에 의해서 잡히는지 확인하는 함수
def promising(x):
    for j in range(x):
        if(col[j] == col[x] or abs(col[j] - col[x]) == (x - j)):
            return 0
    return 1

# 입력 및 출력
n = int(input())
col = [0] * n
count = 0
n_queens(0)
print(count)

 

 

Python으로 돌리면 시간 초과가 나고 Pypy로 돌려야 정답이 뜬다.