[Python] N-Queen (백준 9663번 파이썬)

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

 

문제 풀이

백트래킹 대표 문제인 N퀸 문제입니다. 전에 시도했을 때 어렵게 해결한 경험이 있는데, 백트래킹 연습할 겸 다시 풀어봤습니다.

백트래킹이라는 관점에서 생각하면 그다지 어렵지 않게 해결되는 문제인 것 같습니다.

핵심 포인트는 대각선 방향을 어떻게 처리하냐인데, [행+열], [행-열] 로 처리했습니다.

파이썬이라서 [행-열] 처리가 쉬웠는데, 만약 파이썬이 아닌 다른 언어였다면 [length - (행+열)] 과 같은 방식으로 처리할 수 있을 것 같습니다.

 

문제를 다 푼 후에 보니 v0에 대한 부분은 없어도 괜찮을 것 같습니다.

(어짜피 행을 순차적으로 보므로)

 

# boj 9663 N-Queen

N = int(input())
answer = 0
v0 = [0] * N
v1 = [0] * N
v2 = [0] * (2*N)
v3 = [0] * (2*N)

def dfs(n):
    global answer
    if n == N:
        answer += 1
        return
    for j in range(N):
        if v0[n] == 1 or v1[j] == 1 or v2[n+j] == 1 or v3[n-j]:
            continue
        v0[n] = 1
        v1[j] = 1
        v2[n+j] = 1
        v3[n-j] = 1
        dfs(n+1)
        v0[n] = 0
        v1[j] = 0
        v2[n+j] = 0
        v3[n-j] = 0

dfs(0)
print(answer)