(파이썬) 백준 9663번 "N-Queen"

---

# 답

N = int(input())
ans = 0
chk_col = [False] * N
chk_d1 = [False] * 2 * N  # 대각선 \, 우상단부터 0
chk_d2 = [False] * 2 * N  # 대각선 /, 좌상단부터 0


def bt(row):
    global ans
    if row == N:
        ans += 1
        return
	
    # row가 0이면 왼쪽 절반만 탐색, row가 1 이상이면 전체 탐색
    for col in range(N if row else N // 2):
        if not chk_col[col] and not chk_d1[row - col] and not chk_d2[row + col]:
            chk_col[col] = True
            chk_d1[row - col] = True
            chk_d2[row + col] = True

            bt(row + 1)

            chk_d2[row + col] = False
            chk_d1[row - col] = False
            chk_col[col] = False


if N % 2:
    # 첫 행에 퀸을 왼쪽 절반만 둬 보고 그때의 경우의 수를 2배로 취한다 (정가운데 제외)
    bt(0)
    ans *= 2
	
    # 첫 행의 정가운데에 퀸을 두는 경우를 따로 센다
    col = N // 2
    chk_col[col] = chk_d1[-col] = chk_d2[col] = True
    bt(1)  # row=0 일 때 퀸을 이미 뒀기 때문에 row=1 일 때부터 탐색

    print(ans)

else:
    # 첫 행에 퀸을 왼쪽 절반만 둬 보고 그때의 경우의 수를 2배로 취한다
    bt(0)
    print(ans * 2)

 

 

 

 

---

# 분석 1

 

대표적인 백트래킹 문제입니다.

퀸의 이동 범위는 다음과 같이 상하좌우, 대각선입니다.

 

따라서 각 행에는 1개의 퀸만 놓을 수 있고, 마찬가지로 각 열에는 1개의 퀸만 놓을 수 있습니다.

문제는 대각선입니다. 어떻게 하면 각각의 퀸들이 대각선 방향으로 겹치는지 쉽게 확인할 수 있을까요?

대각선을 ↘ 방향 대각선과, ↙ 방향 대각선으로 나눠서 생각합니다.

 

 

 

5 X 5 체크판이 있다고 하면 대각선은 ↘ 방향, ↙ 방향 각각 9개씩 있습니다.

 

↘ 방향 대각선을 d1이라 하고, 제일 가운데 대각선부터 우측 상단 방향으로 카운팅하겠습니다.

↙ 방향 대각선을 d2이라 하고, 제일 왼쪽 끝 대각선부터 좌측 하단 방향으로 카운팅하겠습니다.

 

 

같은 대각선을 공유하는 좌표들의 공통점은 무엇일까요?

 

 

d2의 2번 대각선을 보겠습니다.

 

2번 대각선에 있는 좌표들은 각각 (0, 2), (1, 1), (2, 0)인데요.

좌표들의 x값과 y값을 더하면 모두 2가 된다는 공통점이 있습니다.

즉, 어떤 좌표 (x, y)가 있을 때, 이 좌표는 x + y번째 d2 대각선을 지난다는 뜻입니다.

 

 

 

그럼 d1은 어떨까요? d1의 2번 대각선을 보겠습니다.

 

2번 대각선에 있는 좌표들은 각각 (2, 0), (3, 1), (4, 2)입니다.

이번에는 x값에서 y값을 빼주세요. 그럼 모두 2가 됩니다.즉, 어떤 좌표 (x, y)가 있을 때, 이 좌표는 x - y번째 d1 대각선을 지나게 됩니다.

 

 

 

 

※ 대각선 번호가 구체적으로 몇 번이냐는 그다지 중요한 문제는 아닙니다.

중요한 건, x좌표와 y좌표를 더하거나(x + y) 뺐을 때(x - y) 나오는 값이 동일한 좌표들은 각각 동일한 대각선을 공유한다는 사실입니다.

 

※ 혹시 x - y 값이 음수가 되더라도 상관없습니다! 파이썬에서는 리스트 인덱싱할 때 음수가 들어가면 뒤에서부터 참조합니다.

L = [0, 1, 2, 3, 4, 5, 6, 7, 8]

print(L[-1])    # 뒤에서 1번째, 8이 출력

 

 

 

 

 

 

---

# 분석 2

 

N개의 퀸을 어떻게 전부 둬서 완성한 모습이 있다고 가정해봅시다.

이 때, 이 완성판을 좌우로 뒤집었을 때 모습 역시 N개의 퀸을 둘 수 있는 방법에 해당합니다.

즉, 한쪽 절반만 탐색하고 나온 가짓 수에 2배를 하면 탐색 시간을 줄일 수 있습니다.

다만 주의할 점이 있습니다. N이 짝수일 때는 문제가 없지만 N이 홀수일 경우 단순히 절반의 2배로 하면 문제가 발생합니다.

그러니 N이 짝수일 때와 홀수일 때를 나눠서 풀어야됩니다.

 

답 코드 중 일부분입니다.

for col in range(N if row else N // 2):

위 코드는 row가 0일 때에만 col이 N의 절반 범위만 탐색하고, row가 1이상이면 N 전체를 탐색합니다.

 

만일 N이 홀수 5이고 row = 0부터 탐색을 시작했다고 가정해봅시다.

row는 0이기 때문에 col은 N의 절반만 탐색합니다. 정확히는 range(N // 2) 범위만 탐색합니다.

5 // 2 == 2이므로, range(N // 2)는 0 ~ 1 범위의 숫자를 생성하죠.

즉 col은 N의 '정가운데를 제외'한 절반만 탐색하게 됩니다.

 

row의 값이 증가하면 col은 다시 N의 전체를 탐색하게 됩니다.

 

한마디로 말하자면 N이 홀수일 경우 첫 번째 행(row == 0)의 정가운데(col == N // 2)에 퀸을 놓는 경우만 쏙 빠진 채로 카운팅됩니다.

그래서 첫 번째 행의 정가운데에 퀸을 놓는 경우의 수를 따로 세 주는 겁니다.