💻 백준 9663번: N-Queen

문제 소개 🧐

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성해야 했다.

입력 📝

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

출력 📤

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

예제 ⌨️

입력

8

출력

92

첫 번째 시도: 클래식 백트래킹 👊

Idea

전통적인 백트래킹 방식으로 문제를 해결하려 했다. 각 행마다 퀸을 하나씩 놓으면서, 다음 행으로 이동할 때 이전에 놓인 퀸들과 충돌하는지 확인하는 방식이었다.

  • cols: 특정 열에 퀸이 이미 놓였는지 확인했다.
  • diag1: row + col 값이 같은 대각선 라인을 확인했다.
  • diag2: row - col 값이 같은 대각선 라인을 확인했다.

이 세 가지 조건을 모두 만족하는 경우에만 퀸을 놓고, 다음 행으로 재귀 호출을 진행했다.

Code

import sys

n = int(sys.stdin.readline().rstrip())

cols = set()   # 사용 중인 열
diag1 = set()  # 아래 대각선 (row+col)
diag2 = set()  # 위 대각선 (row-col)

def backtrack(row, N):
    if row == N:
        return 1

    count = 0
    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)

        count += backtrack(row + 1, N)

        # 백트랙 한번이 성공적으로 끝났으니깐 상태 복원
        cols.remove(col)
        diag1.remove(row + col)
        diag2.remove(row - col)
    return count

print(backtrack(0, N=n))

Result

  • 결과: 시간 초과 😭
  • 분석: Python의 실행 속도와 재귀 호출의 오버헤드로 인해 N이 커질수록 시간이 기하급수적으로 늘어나는 것 같았다.

두 번째 시도: 비트마스킹 최적화 ✨

Idea

시간 초과 문제를 해결하기 위해 AI에게 조언을 구해 비트마스킹을 활용한 최적화 방법을 적용했다. Python도 비트 연산은 C언어 수준으로 빠르다는 점을 이용했다.

  • cols, diag1, diag2를 정수(비트마스크)로 사용하여 퀸의 위치를 기록했다.
  • available 변수는 현재 행에서 퀸을 놓을 수 있는 모든 위치를 비트마스크로 나타냈다.
  • pos = available & -available 연산으로 가장 오른쪽에 있는 ‘1’ 비트(놓을 수 있는 가장 낮은 인덱스의 열)를 찾아냈다.
  • 재귀 호출 시, 대각선 비트마스크는 << 1과 >> 1 시프트 연산을 통해 다음 행의 공격 위치를 효율적으로 계산했다.

Code

import sys

# 표준 입력으로부터 N 읽기
n = int(sys.stdin.readline().rstrip())

# 백트래킹 함수
# row: 현재 퀸을 놓을 행
# cols: 현재 점유된 열 비트마스크
# diag1: ↘ 대각선 점유 비트마스크
# diag2: ↗ 대각선 점유 비트마스크
# N: 체스판 크기
def backtrack(row, cols, diag1, diag2, N):
    # 종료 조건: 모든 행에 퀸 배치 완료
    if row == N:
        return 1  # 하나의 해답 완성

    count = 0
    # 가능한 위치 계산:
    # 1 << N - 1 => N개의 1비트 생성 (0~N-1 열 모두 가능)
    # ~(cols | diag1 | diag2) => 이미 공격받는 위치는 제외
    available = ((1 << N) - 1) & ~(cols | diag1 | diag2)

    # 가능한 위치가 남아 있는 동안 반복
    while available:
        # 가장 오른쪽 1비트 선택 (최하위 비트)
        # pos는 현재 행에서 퀸을 놓을 위치를 나타내는 비트마스크
        pos = available & -available

        # 선택한 위치 제거 → 다음 반복에서 다른 위치 시도
        available -= pos

        # 재귀 호출: 다음 행으로 이동
        # cols | pos: 현재 열 점유 상태 업데이트
        # (diag1 | pos) << 1: 아래 대각선 ↘ 점유 상태 업데이트 (행 증가하면 좌우 이동)
        # (diag2 | pos) >> 1: 위 대각선 ↗ 점유 상태 업데이트 (행 증가하면 좌우 이동)
        count += backtrack(row + 1,
                           cols | pos,
                           (diag1 | pos) << 1,
                           (diag2 | pos) >> 1,
                           N)
    return count  # 현재 분기에서 나온 해답 개수 반환

# 함수 호출 및 결과 출력
print(backtrack(0, 0, 0, 0, n))

Result

  • 결과: 성공! 🎉
  • 분석: 비트 연산을 통해 set 자료구조를 사용할 때보다 훨씬 빠른 속도로 충돌 검사를 수행할 수 있었다.

개선할 부분 및 회고 🤔

  • 비트마스킹을 통해 위치 관련 연산을 처리하는 아이디어가 매우 신선했다. 시간 복잡도가 너무 커지는 문제에서 이 방법을 고려해봐야겠다.
  • 같은 로직이라도 자료구조와 구현 방식에 따라 성능이 크게 달라질 수 있다는 점을 다시 한번 깨달았다.
  • 솔직히 AI 에게 벽을 느꼈다…
  • 관련해서 따로 조사 후 포스팅을 올렸다. (click)
⁂