백준 9663

이 문제는 정말 유명한 N-Queen 문제이다.

퀸은 양옆, 위아래, 대각선 방향 어디든 갈 수 있다.

따라서 한 행에 최대 하나의 퀸이 존재할 수 있다.

이때 N*N 크기의 체스판 위에서 N개의 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다.

만약 N = 8 이라면 위의 그림과 같이 배치할 수 있을 것이다.

 

N-Queen 문제는 dfs, 백트래킹을 필요로 한다.

 

먼저 dfs를 위해 체스판을 표현할 배열이 필요하다.

퀸이 서로 공격할 수 없게 배치하려면 무조건 한 행에는 최대 한 개의 퀸만 존재할 수 있다.

그래서 a_row라는 배열을 만들었는데, 이 배열은 특정 행의 어느 열에 퀸이 위치하는지를 저장한다.

예를 들어 위 그림처럼 1행에서 6열에 퀸이 위치한다면 

a_row[1] = 6 일 것이다.

 

그 후 이 배열을 사용해서 1행부터 N행까지 dfs를 하면 되는데, 이때 백트래킹 과정을 통해 가능성이 없는 경우에는 dfs를 더이상 수행하지 않는다.

1. 같은 열에 퀸이 이미 존재하는 경우

-> a_row 배열 사용 : 만약 a_row[i] 값이 0이 아니라면 i 열에 퀸이 존재하는 것.

2. 대각선 방향에 퀸이 이미 존재하는 경우

-> 이전 행에 존재하는 퀸과의 가로, 세로 거리 비교 : 만약 가로, 세로 거리가 같다면 대각선 방향에 퀸이 존재.

이 두 가지 경우를 가지고 백트래킹을 하면 수행시간을 훨씬 단축할 수 있다.

 

 

예시 코드

import sys
    
N = int(sys.stdin.readline())

# 가능한 경우의 수 
result = 0
a_row = [0]*(N+1)

def DFS(row, N):
    global a_row
    if(row > N):
        global result
        result += 1
    else:
        for i in range(N):
            a_row[row] = i+1
            if(isOkay(row, i+1)):
                DFS(row+1, N)
            else:
                a_row[row] = 0

# 백트래킹 과정
def isOkay(row, col):
    global a_row
    for i in range(1, row):
        # 위
        if(a_row[i] == col):
            return False
        # 대각선
        if(abs(a_row[row]-a_row[i]) == abs(row-i)):
            return False
    return True

# dfs 수행
DFS(1, N)

print(result)