N-Queen 문제와 백트래킹 (1)
크리스가 체스판을 앞에 두고 머리를 쥐어뜯고 있다.
"퀸(Queen)은 가로, 세로, 대각선 어디든 갈 수 있는 최강의 말이잖아. 근데 체스판 위에 퀸 8개를 서로 공격하지 않게 놓으려면 도대체 어떻게 해야 하지?"
이것이 바로 컴퓨터 과학 역사상 가장 유명한 퍼즐 중 하나인 N-Queen 문제다.
단순히 "경우의 수"를 세는 문제가 아니다. 이 문제는 막다른 길에 다다랐을 때 "과감하게 포기하고 되돌아가는(Backtrack)" 지혜를 알려준다.
탐욕 알고리즘이 "후회 없는 직진"이라면, 오늘 배울 **백트래킹(Backtracking)**은 "현명한 후퇴"의 기술이다.
1. 문제: 여왕들의 전쟁을 막아라
N-Queen 문제의 규칙은 간단하다.
만약 이것을 무식하게(Brute Force) 푼다면?
64칸 중에 8칸을 고르는 경우의 수는 약 44억 개다. 이걸 하나하나 다 놓아보고 "어? 공격하네?" 하고 치우는 방식으로는 슈퍼컴퓨터도 지친다.
2. 해결책: 백트래킹 (Backtracking)
백트래킹은 기본적으로 **DFS(깊이 우선 탐색)**를 기반으로 한다. 하지만 멍청하게 끝까지 가지 않는다.
가다가 **"이 길은 가망이 없다(Unpromising)"**고 판단되면, 즉시 발길을 돌려(Backtrack) 부모 노드로 돌아간다. 이를 **가지치기(Pruning)**라고 한다.
크리스의 사고 과정 (4-Queen 예시)
이 과정을 반복하면 44억 번이 아니라 훨씬 적은 횟수(수천 번 내외) 만에 정답을 찾을 수 있다.
3. 자바스크립트로 구현하기
코드가 조금 길어 보이지만, 핵심은 isSafe(검사)와 solve(재귀) 두 부분이다.
(편의상 1차원 배열 board[row] = col 형태로 구현한다. 예: board[0] = 1은 0행 1열에 퀸이 있다는 뜻)
JavaScript
function solveNQueens(n) { const board = new Array(n).fill(-1); // 각 행(index)에 퀸이 놓인 열(value)을 저장 let count = 0; // 1. 유망한지 검사하는 함수 (Promising) function isSafe(row, col) { for (let prevRow = 0; prevRow < row; prevRow++) { const prevCol = board[prevRow]; // 같은 열에 있거나 || 대각선에 있다면 (행 차이와 열 차이가 같으면 대각선임) if (prevCol === col || Math.abs(prevRow - row) === Math.abs(prevCol - col)) { return false; // 공격 받음! 가망 없음. } } return true; // 안전함 } // 2. 재귀적으로 퀸을 놓는 함수 function solve(row) { // 모든 행에 퀸을 다 놓았다면 성공! if (row === n) { count++; return; // 더 깊이 안 가고 돌아감 } // 현재 행(row)의 각 열(col)을 시도 for (let col = 0; col < n; col++) { if (isSafe(row, col)) { board[row] = col; // 퀸을 놓아봄 solve(row + 1); // 다음 행으로 전진 (DFS) // (여기서 함수가 끝났다는 건, 밑에서 실패하고 돌아왔다는 뜻) board[row] = -1; // 퀸을 치움 (Backtracking) } } } solve(0); // 0번째 행부터 시작 return count; } console.log(solveNQueens(8)); // 92 (8x8 체스판의 해답 개수)
4. 백트래킹 vs DFS
많은 사람이 둘을 혼동한다.
백트래킹의 핵심은 **isSafe (가지치기)**에 있다. 이 조건문 하나가 불필요한 탐색 수억 번을 줄여준다.
5. 실전 활용
N-Queen 문제는 실무에서 직접 쓸 일은 없지만, **"제약 충족 문제(Constraint Satisfaction Problems)"**의 기초가 된다.
핵심 정리
이제 우리는 답을 '찾을 수 있는' 문제들은 거의 다 다루었다.
하지만 컴퓨터 과학에는 아무리 똑똑한 알고리즘을 써도 "영원히 풀 수 없을지도 모르는" 악명 높은 문제들이 존재한다.
개발자라면 한 번쯤 들어봤을 전설의 난제, P vs NP 이야기를 마지막으로 알고리즘 여정을 마무리해 보자.
6장의 마지막 주제, "[Algorithm] NP 문제와 브루트 포스: 컴퓨터의 한계에 도전하다" 편에서 계속된다.