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

N-Queen 문제 백트래킹 최적화 및 대각선 처리 방법 정리

N-Queen 문제는 $N \\times N$ 체스판 위에 서로 공격하지 않는 방식으로 $N$개의 퀸을 놓는 경우의 수를 구하는 문제이다.

퀸은 같은 행, 같은 열, 두 대각선 (좌상↘와 우상↙) 방향으로 이동할 수 있으므로, 이를 피하기 위해 배치된 퀸의 열과 대각선 상태를 추적하는 것이 포인트

이번 포스팅에서는 두 가지 접근법으로 문제 해결과 그 해결의 최적화까지 다뤄보겠음. (시간초과로 많이 틀리는 문제)

1. 집합(set)을 활용한 기본 백트래킹
2. 불리언 리스트를 활용한 최적화 백트래킹 (대각선 체크를 $O(1)$에 처리)

---

1. 기본 백트래킹 (Set 사용)

코드

import sys

def main():
    n = int(sys.stdin.readline().rstrip())
    
    # 백트래킹 함수: row번째 행에 퀸을 배치하는 함수
    def backtrack(row):
        # 기저 조건: 모든 행에 퀸을 배치했다면 경우의 수 1 증가
        if row == n:
            nonlocal count
            count += 1
            return
        
        # 현재 행(row)에서 0부터 n-1 까지 각 열(col) 탐색
        for col in range(n):
            # 이미 같은 열 또는 대각선에 퀸이 있다면 패스
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            # 현재 위치에 퀸 배치
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            # 다음 행으로 재귀 호출
            backtrack(row + 1)
            
            # 백트래킹: 배치했던 퀸을 제거하여 원상복구
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    count = 0
    cols, diag1, diag2 = set(), set(), set()
    backtrack(0)
    print(count)

if __name__ == "__main__":
    main()

설명

• 집합(Set) 활용:

  • $cols$는 현재 배치된 퀸의 열 정보를 저장
  • $diag1$는 좌상↘ 대각선을 체크하는 데, 해당 방향의 기준 값인 $row-col$를 저장
  • $diag2$는 우상↙ 대각선을 체크하는 데, $row+col$ 값을 저장

• 백트래킹 방식:

  • 한 행씩 순차적으로 탐색하며 가능한 열을 찾고, 재귀 호출을 통해 다음 행으로 진행
  • 가능한 위치에 퀸을 배치한 후 재귀 호출이 끝나면, 백트래킹을 통해 배치했던 퀸을 제거하여 다른 경우를 탐색

---

2. 최적화 백트래킹 (불리언 리스트 사용)

불리언 리스트를 사용하면 각 열과 대각선의 상태를 즉시 $O(1)$에 확인할 수 있음.
여기서 중요한 부분은 대각선 배열의 크기인데, 대각선 정보를 저장할 배열의 크기를 $2*n-1$로 하는 이유와 보정 방법을 자세히 보자면 아래와 같음.

2-1. 왜 $2*n-1$인가?

좌상↘ 대각선 ($row-col$)

• $row-col$의 값은 체스판에서 최소 $-(n-1)$, 최대 $(n-1)$까지 변할 수 있음.

  예를 들어, $n=4$인 경우를 보면:

  좌표	$row$	$col$	$row - col$
  $(0,0)$	0	0	0
  $(0,1)$	0	1	-1
  $(0,2)$	0	2	-2
  $(0,3)$	0	3	-3
  $(3,0)$	3	0	3

• 값의 범위: -3 ~ 3, 즉 총 $7$가지 값가 있으므로 배열의 크기는 $7 = 2*4-1$이어야 음수값까지도 총 갯수에 넣어 커버할 수 있게 됨.

• 즉, 음수 인덱스를 피하기 위해, 보정을 진행하는 것!

  • 보정 방법: $row-col+(n-1)$
    예를 들어,
    • $row-col=-3$ → $-3+3=0$
    • $row-col=0$ → $0+3=3$
    • $row-col=3$ → $3+3=6$
  • 이렇게 하면 인덱스는 0 ~ 6가 되어 배열 크기 $2*n-1$ (즉, $7$)로 충분히 커버할 수 있게 됨.

우상↙ 대각선 ($row+col$)

• $row+col$의 값은 체스판에서 최소 $0$, 최대 $2(n-1)$까지 변함.

  $n=4$인 경우:

  좌표	$row$	$col$	$row + col$
  $(0,0)$	0	0	0
  $(0,3)$	0	3	3
  $(3,0)$	3	0	3
  $(3,3)$	3	3	6

• 값의 범위: 0 ~ 6, 즉 총 $7$가지 값 → 배열 크기는 역시 $7 = 2*4-1$.

• 음수 없이 자연스럽게 $0$부터 시작하므로 별도의 보정 없이 그대로 사용

2-2. 최적화 코드

import sys

def main():
    n = int(sys.stdin.readline().strip())

    def backtrack(row):
        nonlocal count
        # 모든 행에 퀸을 배치했다면
        if row == n:
            count += 1
            return

        for col in range(n):
            # 해당 열 또는 대각선에 퀸이 있으면 패스
            if colUsed[col] or diag1Used[row - col + (n - 1)] or diag2Used[row + col]:
                continue
            
            # 퀸 배치
            colUsed[col] = diag1Used[row - col + (n - 1)] = diag2Used[row + col] = True
            backtrack(row + 1)
            # 백트래킹: 원상복구
            colUsed[col] = diag1Used[row - col + (n - 1)] = diag2Used[row + col] = False

    count = 0
    colUsed = [False] * n
    # 대각선 배열 크기를 2*n-1로 설정하는 이유:
    # 좌상↘: row-col 값은 -(n-1) ~ sim (n-1) → 보정 후 0 ~ 2*n-2 → 배열 크기: 2*n-1
    # 우상↙: row+col 값은 0 ~ sim 2*(n-1) → 배열 크기: 2*n-1
    diag1Used = [False] * (2 * n - 1)
    diag2Used = [False] * (2 * n - 1)

    backtrack(0)
    print(count)

if __name__ == "__main__":
    main()

표로 정리한 대각선 인덱스 처리

구분	사용 식	값의 범위 (n=4 예시)	보정 여부 및 결과 인덱스 범위
좌상↘ 대각선	$row - col$	-3 ~ 3	보정: $row-col+3$ → 0 ~ 6
우상↙ 대각선	$row + col$	0 ~ 6	보정 불필요 → 0 ~ 6

---

3. 결론

• 문제 해결의 핵심은 각 퀸이 같은 열 또는 대각선에 있는지를 빠르게 판단하는 것
• 불리언 리스트를 사용하면 $O(1)$ 시간 내에 해당 열과 대각선의 사용 여부를 확인할 수 있음.
• 대각선 처리:
  • 좌상↘ 대각선의 경우, $row-col$ 값이 음수가 될 수 있으므로, $row-col+(n-1)$로 보정하여 배열 인덱스로 사용
  • 우상↙ 대각선은 $row+col$ 그대로 사용
• 배열 크기:
  • 두 대각선 모두 값의 범위가 $0 \\sim 2*n-2$이므로, 배열 크기를 $2*n-1$로 설정하여 모든 경우를 커버함.