[Baekjoon 9663] N-Queens

문제

💛Ⅳ [Baekjoon 9663 - N-Queens]

문제 풀이 방법

이 문제는 백트래킹의 대표 문제이다. N-Queens문제는 C언어로 처음 풀어보았는데 구현하기 위한 아이디어를 떠올리기가 어려웠던 문제로 기억한다. 이번에 파이썬으로 더 간단하게 구현해보면서 아이디어를 더 정확하게 이해할 수 있었다!

우선 이 문제는 N*N 체스판이여서 이차원 배열로 접근할 수 있지만 일차원 배열로 풀이하는 것이 더 효율적이다.

1. board라는 N개의 인덱스를 가진 일차원 배열을 선언한다. 이 때, board의 인덱스는 행을 의미하고, 각 인덱스에 들어가는 번호는 퀸을 둔 열을 의미한다.
2. 현재 퀸을 두고자하는 행에 반복문을 돌며 각 열마다 퀸을 놓는다.
   1. 그 자리에 퀸을 둘 수 있는지 즉, 같은 열 또는 대각선에 퀸이 존재하는지를 promising 함수를 통해 체크한다.
   2. 퀸을 둘 수 있다면, 행 인덱스에 +1을 하여 다음 행에 퀸을 놓는다. (재귀 호출)
3. 마지막 행까지 퀸을 모두 놓는다면 answer + 1을 한다.

풀이 코드

Python

import sys
input = sys.stdin.readline

N = int(input())
board = [-1]*N
answer = 0

def promising(col):
    for c in range(col):
        if board[c] == board[col] or abs(c-col) == abs(board[c]-board[col]):
            return False
    return True

def nQueens(row):
    global answer
    if row == N:
        answer += 1
        return
    for c in range(N): # 각 열마다 Queen 놓기
        board[row] = c
        if promising(row):
            nQueens(row+1)

nQueens(0)
print(answer)