[Python] 백준 9663 N-Queen

문제 바로가기

   문제분석   

#  N개의 퀸이 N X N 크기의 체스판에 놓여야 하므로, 퀸들이 각 행마다 반드시 1개씩 존재해야 하고 따라서 행, 즉, 좌우는 확인할 필요가 없다.

# 확인해야 할 남은 방향은 열기준인 상, 하와 대각선

• 열의 경우 길이가 N인 1차원 배열을 만들어 체크
• 대각선의 경우, 퀸을 기준으로 ↗, ↙ 이 두 가지 방향은 현재 인덱스의 합이 해당 대각선 방향 각각의 인덱스의 합들과 같다는 규칙이 있었음

# 따라서 길이가 N * 2 -1인 1차원 배열로 체크 가능

# 나머지 ↖, ↘ 이 두 방향의 경우도 똑같은 원리로 인덱스 제어 변수가 i, j라고 쳤을 때 i-j+N-1이라는 규칙이 성립

 

 

   문제풀이   

import sys
input = sys.stdin.readline
 
def dfs(i):
    global N, col, slash, backSlash, case
    if i == N:
        case += 1
        return
    for j in range(N):
        if not (col[j] or slash[i + j] or backSlash[i - j + N - 1]):
            col[j] = slash[i + j] = backSlash[i - j + N - 1] = True
            DFS(i + 1)
            col[j] = slash[i + j] = backSlash[i - j + N - 1] = False
 
 
N = int(input())
col, slash, backSlash = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)
case = 0
 
dfs(0)
 
print(case)

 

참고자료 : https://hellominchan.tistory.com/176