N-Queen

백준 9663: N-Queen

시간 제한: 10 초

메모리 제한: 128 MB

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

풀이

그 유명하다는 N-Queen 문제이다.

N-Queen 문제의 규칙은 간단하다. N by N 정사각형 체스판에 Queen들이 서로를 공격하지 못하게 말을 놓으라는 거다.

그런데 필자는 체스를 단 한판도 두어 본적이 없다. 그래서 나무위키에 검색을 해보니 Queen은 말이 위치한 곳에서 팔방(8방)으로 공격이 가능하다.

그림으로 나타내면 다음과 같다.

그림이 못 생기긴 했지만, 글과 연계해서 보면 이해가 될 것이다.

오케이, 규칙을 대강 알겠다. 그럼 체스판의 각 행마다는 Queen이 무조건 1개밖에 못 올 것이고, 가장 위의 행부터 훑으면서 각 행에 한개의 Queen을 놓으면되고, 그 다음 행에 Queen을 놓을 때는 위의 행에 놓았던 Queen의 대각선 방향을 조심하면 되겠다.

어떻게 풀면 될까..? 나는 밑의 4문제를 참고해서 풀었다.
백준 15649번
백준 15650번
백준 15651번
백준 15652번

위 4문제들을 풀면서 썼던 발상을 N-Queen 문제에 그대로 적용했다. (1, 2, 3, 4는 각 행의 열 번호를 의미한다.)

위의 그림과 같이 1, 2, 3, 4를 이용해 tree를 구성하고, dfs와 backtracking 이용해 경우의 수를 조사하고, 조건에 맞지 않으면 다시 위의 level로 올라가고 다른 경우의 수를 조사한다.

경우의 수를 조사할 때는 stack을 이용한다. 코드를 보자.

n = int(input())
cnt = 0
queen_col_pos = [ -1 for _ in range(15)]

def is_promising(n, level):

    if n in queen_col_pos:
        return False
    
    for i in range(level):
        if abs(n - queen_col_pos[i]) == level - i:
            return False
    
    return True

def dfs(level):

    if level == n:
        global cnt
        cnt += 1
        return
    
    for i in range(n):
        if is_promising(i, level) == False:
            continue
            
        queen_col_pos[level] = i
        dfs(level + 1)
        queen_col_pos[level] = -1

dfs(0)
print(cnt)

참고로 PyPy3로 돌리니 시간제한에 안 걸린다. Python3로 돌리니 시간제한에 걸렸었다.