[알고리즘] 백준 9663 N-Queen / python, 백트랙킹

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

9663번: N-Queen

 

✔ 풀이과정

같은 열과 대각선에 안겹치게 퀸을 놓는 게임을 구현한다.

 

먼저, 같은 열을 체크한다. ck배열은 크기가 N이고, 퀸을 놓은 위치의 열을 표시한다. ck_col[2] = 1

 

대각선을 체크한다. 대각선의 총 개수는 7개 이므로 ck배열의 크기는 2 * N - 1 이다.

퀸을 놓은 대각선의 규칙을 찾아보면 위치가 행=1, 열=2 일 때 3이므로 ck_dig[행+열] = 1로 바꾼다.

 

반대쪽 대각선을 체크한다. 대각선의 총 개수는 7개 이므로 ck배열의 크기는 2 * N - 1 이다.

퀸을 놓은 대각선의 규칙을 찾아보면 위치가 행=1, 열=2 일 때 2이므로 ck_dig[행-열+N-1] = 1로 바꾼다.

 

ck배열들이 1인지 확인하면서 dfs로 퀸을 놓을 위치를 찾는다.

 

def ck(row, col):
    if ck_col[col] == 1:
        return False
    if ck_dig[row + col] == 1:
        return False
    if ck_dig2[row - col + N-1] == 1:
        return False
    return True

def dfs(row):
    if row == N:
        return 1
    result = 0
    for col in range(N):
        if ck(row, col):
            D[row][col] = 1
            ck_col[col] = 1
            ck_dig[row + col] = 1
            ck_dig2[row - col + N-1] = 1
            result += dfs(row + 1)
            D[row][col] = 0
            ck_col[col] = 0
            ck_dig[row + col] = 0
            ck_dig2[row - col + N-1] = 0
    return result

N = int(input())
D = [[0]*N for _ in range(N)]
ck_col = [0] * N
ck_dig = [0] * (2*N-1)
ck_dig2 = [0] * (2*N-1)
print(dfs(0))