[BOJ / 9663] 백트래킹 느렸다면? 비트마스크로 최적화하는 N-Queen 문제 #비트마스크 #백트래킹

#알고리즘 #백준 #N-Queens #비트마스크 #백트래킹

 

✅ 문제 설명

✅ 해결 방법

✅ 발생한 문제와 방안

✅ 최종적인 해결 방법

✅ 최적화 방안

그래서 오늘의 TIL(Today I Learned) 학습 키워드

✨ 2의 보수와 덧셈 회로의 역사

✨ 비트마스크 기반 백트래킹 최적화

✨ x & -x 트릭 (오른쪽 1비트 추출)

✅ 문제 설명

N개의 퀸(Queen)을 N×N 크기의 체스판 위에 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제. 퀸은 같은 행, 열, 그리고 대각선 방향으로 움직일 수 있기 때문에, 모든 퀸은 서로 다른 행, 열, 대각선 위에 놓여야 한다.

✅ 해결 방법

처음에는 순열 기반의 백트래킹을 구현해서, 한 행마다 열을 하나씩 고르고, 모든 순열마다 isValid()로 대각선 충돌 여부를 검사했다. 하지만 N이 커질수록 (N ≥ 12) 시간 초과가 발생했고, 이는 N!의 탐색량 때문이었다.

그래서 비트마스크 방식으로 최적화를 시도했다. 열과 대각선을 각각 비트 플래그로 표현하고, 가능한 자리만 비트로 연산하여 재귀적으로 탐색한다. 이 방식은 가지치기(Pruning) 효과가 매우 커서 N=14도 빠르게 통과된다.

✅ 발생한 문제와 방안

2의 보수를 활용하는 과정에서 가장 신기했던 부분은 -x를 계산할 때 ~x + 1을 사용하는 방식이었다. 처음에는 왜 반전(~) 후 +1을 해야만 하는지 이해가 어려웠지만, 결국 carry(자리 올림)가 자동으로 정리되어 덧셈만으로 뺄셈이 구현된다는 사실을 깨달았다.

또한, x & -x 연산이 가능한 위치 중 가장 낮은 비트(오른쪽에서 가장 오른쪽의 1)만 추출한다는 점이 정말 인상 깊었다. 단순히 -x를 했을 뿐인데, 정확하게 "이번 탐색 대상"을 O(1)에 고를 수 있다는 점에서 비트마스크의 위력을 체감했다.

✅ 최종적인 해결 방법

const N = +require("fs").readFileSync("/dev/stdin").toString().trim();
let answer = 0;

function dfs(row, cols, diag1, diag2) {
  if (row === N) {
    answer++;
    return;
  }

  let available = ~(cols | diag1 | diag2) & ((1 << N) - 1);

  while (available) {
    const pos = available & -available;
    available ^= pos;
    dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1);
  }
}

dfs(0, 0, 0, 0);
console.log(answer);

✅ 최적화 방안

• 열/대각선 체크를 배열 대신 정수 비트로 관리 → 공간 절약 + 비교 연산을 O(1)로 단축
• for문 대신 비트연산으로 가능한 위치 선택 → x & -x를 활용
• carry 처리 생략 → 어차피 넘치는 비트는 버려도 정답이 유지됨

---

AI로 작성한 실험적인 글입니다.

 

 

---

안녕하세요, 위 모든 글은 AI를 활용한 학습 기법을 요약한 일종의 템플릿이자 요약본입니다.

(저는 사람이에요... !)

블로그 자동화를 위한 템플릿으로 무엇이 있을까 싶어서, 우선적으로 적용해보고 있는데요.

구현 난이도를 위해서는 정형화된 틀이 있어야하고, 항상 반복되는 재학습을 위한 rawData도 필요하여

곰곰이 생각해보니 요즘 알고리즘도 재미가 들렸겠다. 적용해보고 있습니다.

 

나중에 데이터가 쌓이면 톤앤보이스도 적용해보면 좋겠네요.

markdown으로는 잘 만들어지는 거 같아서. 템플릿은 유지보수를 위해 다른 게시글에 따로 정리하도록 하겠습니다.

감사합니다 !