BOJ9663 N-Queen

문제

BOJ9663 N-Queen
골드V | 백준 9633 | Python3 파이썬 풀이

알고리즘

전형적인 백트래킹 문제이다. DFS는 그래프 완전탐색이지만, 시간을 줄이기 위해서 자식으로의 탐색이 의미 없는 경우 다시 부모로 거슬러올라와 다른 자식을 탐색하여 시간을 줄인다. (가볼 가치가 없는 자식 노드로 방문하지 않는 것이다)

DFS는 단순하게 모든 대각선 방향으로 갈 수 있는 곳을 체크한다. 만약 자식 노드에서 탐색하던 중 불가능한 경우가 생긴다면 다시 부모로 올라오고, 자식이 시도한 경우는 삭제한다.

if not checked:
    continue

# 바꿔보고
DP[idx][i] = 1
# 자식 탐색
DFS(idx + 1)
# 자식 탐색이 실패하면 복구
DP[idx][i] = 0

백트래킹 알고리즘에 대해 잘 설명해놓으신 글
[알고리즘] 되추적(Backtracking)을 알아보자.

코드

import sys

N = int(input())

DP = [[0 for _ in range(N)] for _ in range(N)]
count = 0

def DFS(idx):
    if idx == N:
        global count
        count += 1
        return

    for i in range(N):
        checked = True
        for j in range(idx):
            if DP[j][i] == 1:
                checked = False
                break
        
        # ↖
        if checked:
            row = idx
            col = i
            while row >= 0 and col >= 0:
                if DP[row][col] == 1:
                    checked = False
                    break

                row -= 1; col-=1

        # ↗
        if checked:
            row = idx
            col = i
            while row >=0 and col < N:
                if DP[row][col] == 1:
                    checked = False
                    break

                row -= 1; col += 1

        if not checked:
            continue

        DP[idx][i] = 1
        DFS(idx + 1)
        DP[idx][i] = 0


DFS(0)
print(count)

결과

이 문제에는 편법이 존재한다. (골드V임에도 불구하고) 경우의 수가 매우 적기에 모든 경우를 미리 구해놓은 경우 아주 빠르고 짧은 코드로 통과가 가능하다.

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