[백준 9663번] N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

유명한 백트래킹 완전 탐색 문제라고 해서 풀어봤다. Python3로 풀면 시간 초과가 나서 PyPy3로 제출했다.

# 1 <= N <= 15

import sys

readline = sys.stdin.readline

N = int(readline())

row = [-1 for _ in range(N)]  # row[i] = j: i행 j열에 퀸이 있다.


def dfs(row_index, count):
    if row_index == N:
        count += 1
        return count

    for col_index in range(N):
        row[row_index] = col_index
        if is_promising_position(row_index, col_index):
            count = dfs(row_index + 1, count)
    return count


def is_promising_position(row_index, col_index):
    for i in range(row_index): # 0행부터 차례대로 배치하므로, 위쪽 테이블만 확인하면 된다.
        if col_index == row[i]: # 같은 열에 퀸이 존재할 경우
            return False
        if row_index - i == abs(col_index - row[i]): # 대각선 방향에 퀸이 존재할 경우
            return False
    return True


print(dfs(0, 0))

count를 global 변수로 만들어도 된다.

백트래킹은 탐색을 할 때, 해가 없는 경우 다시 되돌아가서 해를 찾는 기법을 말한다. 보통 dfs로 모든 경로를 탐색하며, 조건에 맞지 않아 해가 있을 가능성이 없으면 백트래킹한다. 이런 최적화 기법을 가지치기(pruning)라 한다.

사실 문제를 보면 N이 15까지니까 탐색해도 되겠구나.. 라는 생각이 들긴 하는데, 대각선 요소를 판별하는 조건을 찾기가 어려웠다. 새벽에 풀어서 그런가;;

현재 위치를 (i, j)라 했을 때, 대각선 요소는 (i - k, j - k) 또는 (i - k, j + k) 위치에 속한다. 따라서 row_index끼리의 차이와 column_index 끼리의 차이가 같다.