[백준] 9663. N-Queen python

🐳 링크

백준 N-Queen

🐕 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

🐾 풀이 방법

n_queen 함수를 실행시킬 때에는 열을 이용해서 실행시키고, 들어간 순서대로를 행으로 배정하여 같은 열에 있는 노드와 대각노드를 제외한다.

예를 들자면, n=4인 경우
0,1,2,3 순으로 n_queen함수를 실행시키게 된다.
이때 arr에 [0,1] 이 들어가있다면, 이는 (0,0), (1,1)에 퀸이 놓여있다는 것을 의미한다.
따라서 n_queen 함수 내에서 같은 열에 위치 즉, 현재 arr값과 같은 값이면 제외하고 distance를 구해서 대각노드도 제외하는 방법으로 이 문제를 해결할 수 있다.

소스코드 (Pypy3)

import sys

def n_queen(arr, n):
    global count
    if len(arr) == n:
        count += 1
        return
    candidate = list(range(n)) #n=4인 경우, candidate=[0,1,2,3]
    for i in range(len(arr)): #i는 어쩌면 행 번호
        if arr[i] in candidate:
            candidate.remove(arr[i])
        dist = len(arr) - i
        # arr[i]가 아닌 len(arr)로 하는 이유는, 다음 차례에 들어갈 칸이 현재 들어가있는 행길이 뒤에 들어가야하므로, 대각선의 차가 그만큼 나야한다.
        # 예를 들어서 현재 (0,0)만 arr에 있는 경우에는 다음에 놓일 퀸은 1행에 들어가게 되므로 대각선에 해당하는 값은 (1,1)밖에 없으므로 dist=1
        # 현재 (0,0) (1,2) 가 들어가있는 경우에는 (0,0)에서 확인하는 경우라도 다음에 놓일 퀸은 2행에 들어가게 되므로 대각선에 해당하는 값은 (2,2) 이르모 dist = 2 (len(arr)-i)
        if arr[i] + dist in candidate: #같은 대각선
            candidate.remove(arr[i] + dist)
        if arr[i] - dist in candidate:
            candidate.remove(arr[i] - dist)
    if candidate:
        for c in candidate:
            arr.append(c)
            n_queen(arr,n)
            arr.pop()
    else:
        return

count = 0
n = int(sys.stdin.readline().strip())
for i in range(n):
    n_queen([i], n)
print(count)