[BOJ] 9663번: N-Queen

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

9663번: N-Queen

 

Python3

체스판에서 퀸이 놓여질 때 서로 공격할 수 없게 놓아야한다. 퀸이 공격할 수 있는 상황은 1. 같은 행에 다른 퀸이 위치할때, 2. 같은 열에 다른 퀸이 위치할 때, 3. 대각선상에 다른 퀸이 위치할 때 3가지 경우이다.

이는 백트랙킹으로 해결 할 수 있다. 먼저 퀸을 행 중 한 열에 놓은 후 다음 퀸의 위치를 택하는 상황을 연쇄적으로 하면 된다.

예를 들어보자!

Q	x	x	x

Q	x	x	x
x	x	Q	x

Q	x	x	x
x	x	Q	x
x	x	x	x

=> 실패 BACK!

 

Q	x	x	x
x	x	x	Q
x	Q	x	x

Q	x	x	x
x	x	x	Q
x	Q	x	x
x	x	x	x

=> 실패 BACK!

 

x	Q	x	x

x	Q	x	x
x	x	x	Q

x	Q	x	x
x	x	x	Q
Q	x	x	x

x	Q	x	x
x	x	x	Q
Q	x	x	x
x	x	Q	x

성공!

 

위와 같은 방식으로 계속 진행하게 된다.

 

def is_exist(q):
    for i in range(q):
        if queen[q] == queen[i] or abs(queen[q]-queen[i]) == q - i:
            return False
    return True


def dfs(q):
    global result
    if q == N:
        result += 1
    else:
        for i in range(N):
            queen[q] = i
            if is_exist(q):
                dfs(q+1)


if __name__ == '__main__':
    N = int(input())
    queen = [0]*N
    result = 0
    dfs(0)
    print(result)

 

dfs에서는 현재 행에서 퀸의 위치를 지정한다. is_exist에서는 퀸의 위치 지정을 위해 주변에 퀸이 있는지 확인한다. 

이 코드에서 중요한 점은 행 개수의 1차원 배열을 사용한다는 것이다. 1차원 배열의 index를 row라고 생각하고 퀸의 열을 해당 index에 저장한다. 이러한 방식으로 굳이 2차원 배열을 만들지 않아도 문제 해결이 가능하다.