N-퀸 문제란?
N-퀸(N-Queens)은 N×N 체스판에 퀸 N개를, 서로 공격하지 못하게 놓는 방법(또는 그 경우의 수)을 찾는 문제입니다. 퀸은 같은 행·같은 열·두 대각선을 따라 공격하므로, 어떤 두 퀸도 행·열·대각선을 공유하면 안 됩니다. 백트래킹의 교과서적 예제입니다.
핵심 한 줄: "한 행에 퀸 하나씩, 안 되면 되돌아온다." 모든 배치를 무작정 시도하는 대신, 막히는 순간 빠르게 포기하고 다른 선택으로 돌아갑니다.
핵심은 백트래킹
각 행에 퀸을 하나씩 놓는다고 정하면, 같은 행 충돌은 자동으로 사라집니다. 남은 건 열과 대각선뿐입니다.
백트래킹은 이렇게 동작합니다 — 현재 행에서 안전한 열에 퀸을 놓고 다음 행으로 재귀해 들어가다가, 놓을 자리가 없으면(막히면) 방금 놓은 퀸을 거두고 이전 행으로 되돌아와 다른 열을 시도합니다.
가지치기(pruning)
매번 판 전체를 검사하면 느립니다. 열 사용 여부, 두 대각선 사용 여부를 불리언 배열로 기록해 두면, 한 자리의 안전성을 O(1)에 판단할 수 있습니다.
- •같은 열:
col[c] - •↘ 대각선:
row + col이 같음 - •↙ 대각선:
row - col이 같음 (음수 방지 위해+N-1보정)
불가능한 가지를 즉시 잘라내므로 탐색량이 크게 줄어듭니다.
동작 원리
1단계. row = 0부터 시작합니다.
2단계. 현재 행의 각 열 c에 대해, 열·두 대각선이 비어 있으면 퀸을 놓고 표시한 뒤 row + 1로 재귀합니다.
3단계. 재귀가 끝나면(성공이든 실패든) 표시를 지우고 퀸을 거둡니다(백트래킹) — 다음 열을 공정하게 시도하기 위해서입니다.
4단계. row == N에 도달하면 N개를 모두 놓은 것이므로 해 하나를 완성합니다.
알고노트 시각화는 퀸이 놓이고, 막혀서 되돌아오며 거둬지는 과정을 색으로 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | 최악 O(N!) 부근(가지치기로 크게 감소) |
| 공간 | O(N) |
가지치기 덕분에 실제 탐색은 N!보다 훨씬 적습니다.
예시로 따라가기
4-퀸:
- •(행0,열0)에 놓음 → 행1은 열2만 안전 → 행2는 안전한 곳 없음 → 되돌아감
- •(행0,열1)에 놓음 → 행1 열3 → 행2 열0 → 행3 열2 → 해 완성
- •4-퀸의 해는 총 2개입니다.
자주 하는 실수
- •대각선 인덱스:
row+col과row-col(+N-1 보정)을 헷갈리면 충돌 검사가 어긋납니다. - •상태 복원 누락: 재귀에서 돌아온 뒤 열·대각선 표시와 퀸을 반드시 되돌려야 합니다(백트래킹의 핵심).
- •목표 혼동: "경우의 수"인지 "한 가지 배치"인지에 따라 멈추는 조건이 다릅니다.
알고노트에서 직접 확인하세요
퀸이 한 행씩 놓이고, 막히면 이전 행으로 되돌아와 다른 열을 시도하는 백트래킹 과정을 알고노트에서 단계별로 확인할 수 있습니다.