[Python - Backtracking] 9663 N-Queen

📌 문제

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

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

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

백트래킹의 꽃인 N-Queen 문제이다. N-Queen이 가능한 모든 경우를 탐색해야 한다.

👨‍🏫 문제 풀이

📄 전체 코드

n = int(input())

flag_1 = [0] * n
flag_2 = [0] * (2 * n - 1)
flag_3 = [0] * (2 * n - 1)

cnt = 0


def nQueen(depth):
    global cnt
    if depth == n:
        cnt += 1
        return

    for i in range(n):
        if not(flag_1[i] or flag_2[i + depth] or flag_3[n + depth - i - 1]):
            flag_1[i], flag_2[i + depth], flag_3[n + depth - i - 1] = 1, 1, 1
            nQueen(depth + 1)
            flag_1[i], flag_2[i + depth], flag_3[n + depth - i - 1] = 0, 0, 0


nQueen(0)
print(cnt)

📄 준비

n = int(input())

flag_1 = [0] * n
flag_2 = [0] * (2 * n - 1)
flag_3 = [0] * (2 * n - 1)

cnt = 0

flag는 해당 위치 놓을 수 있는지 라인을 파악하기 위한 리스트이다.

 

flag_1은 가로 방향, flag_2는 좌하우상 대각선, flag_3은 좌상우하 대각선에 퀸이 있는지 체크하는 리스트이다.

 

세로 방향을 설정하지 않은 이유는 for문으로 탐색할 것이기 때문에 어차피 설정할 필요가 없어서다.

📄 풀이

def nQueen(depth):
    global cnt
    if depth == n:
        cnt += 1
        return

    for i in range(n):
        if not(flag_1[i] or flag_2[i + depth] or flag_3[n + depth - i - 1]):
            flag_1[i], flag_2[i + depth], flag_3[n + depth - i - 1] = 1, 1, 1
            nQueen(depth + 1)
            flag_1[i], flag_2[i + depth], flag_3[n + depth - i - 1] = 0, 0, 0


nQueen(0)
print(cnt)

모두 가능한 경우라면 그 라인에 방문표시를 해둔다. flag_1은 가로방향이라서 바로 i를, flag_2는 좌측 상단에서부터 우측 하단까지의 라인을 체크하는 것이라서 여태 진행한 열 + 카운팅 변수 i를 해서 체크하고, flag_3도 같은 이유로 위와 같이 체크했다.

 

더 깊이 들어가도록 재귀를 하고, 재귀를 벗어나면 방문해제하여 모든 가능한 수를 체크하도록 한다.

📌 총평

이걸 처음 푼 사람은 정말 괴물일까? 대단하다.