[백준] (9663) N-Queen [Python]

🔗 문제 링크

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

💻 코드 구현

def remove_queen(i, j):
    for k in range(n):
        board[i][k] -= 1
        board[k][j] -= 1
        if i + k < n and j + k < n:
            board[i+k][j+k] -= 1
        if i - k >= 0 and j - k >= 0:
            board[i-k][j-k] -= 1
        if i + k < n and j - k >= 0:
            board[i+k][j-k] -= 1
        if i - k >= 0 and j + k < n:
            board[i-k][j+k] -= 1
            
def set_queen(i, j):
    for k in range(n):
        board[i][k] += 1
        board[k][j] += 1
        if i + k < n and j + k < n:
            board[i+k][j+k] += 1
        if i - k >= 0 and j - k >= 0:
            board[i-k][j-k] += 1
        if i + k < n and j - k >= 0:
            board[i+k][j-k] += 1
        if i - k >= 0 and j + k < n:
            board[i-k][j+k] += 1

def queen(i, j):
    global answer

	# 해당 보드칸에 퀸을 놓을 수 없는 경우
    if board[i][j] > 0:
        return
    
    set_queen(i, j)
    
    # 성공적으로 마지막 번째 퀸까지 보드판에 놓은 경우
    if j+1 == n:
        answer += 1
        remove_queen(i, j)
        return

	# 현재 열에 대해서 모든 경우의 수 탐색
    for k in range(n):
        queen(k, j+1)
        
    # 재귀함수 실행 완료 후, 같은 열의 다른 칸에 퀸을 놓기 위해 현재 퀸 제거
    remove_queen(i, j)
            
n = int(input())
answer = 0
board = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    queen(i, 0)
print(answer)

🔍 코드 분석

Python으로 실행했을 때 시간 초과가 걸렸기 때문에, 일반적으로 파이썬보다 더 빠르다고 알려진 Pypy3으로 돌렸더니, 136384 KB의 메모리와 15932 ms의 시간이 소요되었다.

---

🤯 더 간단한 코드?

def queen(i):
    global answer

    if i == n:
        answer += 1
        #print("YES")
        return

    for j in range(n):
        if v1[j] == v2[i+j] == v3[i-j] == 0:
            v1[j] = v2[i+j] = v3[i-j] = 1
            #print(f"i = {i}, j = {j}")
            queen(i+1)
            v1[j] = v2[i+j] = v3[i-j] = 0
            #print("BOOM")

n = int(input())
v1 = [0] * n
v2 = [0] * (2 * n)
v3 = [0] * (2 * n)
answer = 0
queen(0)
print(answer)

👨‍🔬 코드 해설