BOJ 9663: N-Queen [Python 3]

오늘의 문제는 Well-known Problem으로 평가받는 N-Queen이다.

국내외를 막론하고 각종 언어로 solution이 유튜브에서부터 다양한 검색사이트에 나열되어 있을 정도이다.

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

9663번: N-Queen

이 문제는 DFS를 통하여 구현하였다.

n=int(input())
chessBoard=[1e10]*n
ans=0
def dfs(idx):
    global ans
    if idx==n:
        ans+=1
        return
    for i in range(n):
        flag=0
        if i not in chessBoard:
            count=1
            while idx-count>=0:
                if chessBoard[idx-count]==i-count or chessBoard[idx-count]==i+count:
                    flag=1
                    break
                count+=1
            if not flag:
                count=1
                while idx+count<n:
                    if chessBoard[idx+count]==i-count or chessBoard[idx+count]==i+count:
                        flag=1
                        break
                    count+=1
            if not flag:
                chessBoard[idx]=i
                dfs(idx+1)
                chessBoard[idx]=1e10
dfs(0)
print(ans)

Chess에서는 Queen이라는 말이 있다.

Queen은, 상하좌우, 대각선 모든 방향으로 원하는 길이만큼 이동할 수 있다.

 

해당 코드에 대한 설명이다.

ChessBoard는 각 행의 몇 번째 열에 Queen이 위치하였는지를 알려주는 데이터이다.

먼저 ChessBoard에 큰 임의의 숫자 1e10을 넣는다. (Queen을 아직 두지 않았기 때문)

dfs라는 함수에서는, 재귀를 통해 Queen을 한 자리, 한 자리 두면서 문제를 해결한다.

idx는 행, i는 열을 의미한다.

행을 하나씩 내리면서, Queen의 위치를 부여한다.

 

 

먼저, 해당 열에 이미 Queen이 있는지 확인한다.

해당 행은 확인 할 필요가 없는데, 왜냐하면 이미 한 행에 두 개의 Queen이 있을 수 없기 때문이다.

이후, 현재 정해져 있는 좌표에서 Queen이 대각선으로 이동하였을 때 다른 Queen을 만날 수 있는지 확인한다.

 

해당 문제의 가능한 예시이다.

n이 4일 때,