N-Queen 백트래킹:

N-Queen 문제에 도전했습니다. 처음에는 N x N 보드를 직접 만들고 퀸을 배치하는 방식으로 접근하려 했지만, 이는 매우 비효율적인 길임을 깨닫고 완전히 새로운 관점에서 문제에 접근하게 되었습니다. 오늘 학습 내용을 통해 N-Queen 문제를 어떻게 "수학적 제약 조건"으로 바꾸고, 효율적인 백트래킹 알고리즘을 설계하는지 자세히 알아보겠습니다.

학습 주제

• 오늘 공부한 주제: N-Queen 문제 백트래킹 알고리즘
• 오늘의 질문: N-Queen 문제, 백트래킹으로 푸는 N x N 보드 문제
• 학습 날짜: 2026년 2월 6일

질문과 탐구

처음에는 N x N 보드를 만들고, 각 칸에 퀸을 하나씩 놓으면서 보드를 칠하는 방식으로 공격 영역을 표시해야 한다고 생각했습니다. 퀸을 놓고, 공격하는 칸들을 전역 변수로 표시하고, 재귀 호출 후에는 다시 원래 상태로 복구하는 방식이었습니다. 하지만 이 방식은 "상태 복구"가 너무 복잡하다는 것을 알게 되었습니다.

이러한 혼란 속에서 저는 다음과 같은 질문들을 던지며 탐구를 시작했습니다.

• N-Queen 문제를 정말 보드를 만들어서 풀어야 할까?
• 보드를 칠하지 않고 어떻게 공격 범위를 효율적으로 체크할 수 있을까?
• row - col과 row + col이 어떻게 대각선과 연결되는 걸까?
• 배열 크기 30은 어디서 나온 걸까?

핵심 학습 내용

가장 핵심적인 전환점은 **"보드를 만들 필요가 없다"**는 사실을 깨닫는 순간이었습니다.

1. 문제 재정의: 보드 → 좌표 제약

N-Queen 문제의 핵심은 N x N 보드를 시뮬레이션하는 것이 아니라, **"서로 충돌하지 않는 N개의 좌표 집합을 세는 문제"**로 재해석하는 것입니다.

• 행(row)의 제약: 퀸은 각 행에 하나씩만 놓을 수 있습니다. 이는 재귀 호출에서 row를 0부터 N-1까지 순차적으로 증가시키는 것으로 자연스럽게 처리됩니다.
• 열(col)의 제약: 같은 열에 두 퀸을 놓을 수 없습니다. 이를 usedCol[col] 배열로 관리합니다.
• 대각선 제약:
  • \ 방향 대각선: row - col 값이 일정합니다.
  • / 방향 대각선: row + col 값이 일정합니다.

이를 바탕으로 다음과 같은 상태 변수만으로 문제를 해결할 수 있게 됩니다.

bool usedCol[15];        // 현재 열에 퀸이 있는지
bool usedDiag1[30];      // '\' 대각선 그룹 ID 사용 여부
bool usedDiag2[30];      // '/' 대각선 그룹 ID 사용 여부

2. 대각선 수학의 이해

row - col과 row + col이 어떻게 대각선을 나타내는지 처음에는 혼란스러웠습니다. 하지만 좌표계와 수학적 정의를 통해 명확히 이해할 수 있었습니다.

• row - col: row와 col이 모두 증가하는 \ 방향 대각선에서 이 값은 일정하게 유지됩니다. (예: (0,0), (1,1), (2,2) → row - col = 0)
• row + col: row가 증가하고 col이 감소하는 / 방향 대각선에서 이 값은 일정하게 유지됩니다. (예: (0,2), (1,1), (2,0) → row + col = 2)

row - col의 범위가 음수가 될 수 있기 때문에, 배열 인덱스로 사용하기 위해 +(N-1)을 더해 양수 범위로 만들어줍니다. (예: row - col + (N-1))

3. 백트래킹 재귀 구조

dfs(row) 함수는 "현재 row번째 행에 퀸을 놓을 수 있는 모든 경우를 시도한다"는 의미를 가집니다.

• 종료 조건: row == N 이 되면, 모든 행에 퀸을 성공적으로 배치했다는 의미이므로 정답을 하나 증가시킵니다.
• 재귀 단계: 현재 row에 대해 가능한 모든 col을 시도합니다.
  • if (usedCol[col] || usedDiag1[d1] || usedDiag2[d2]) continue;: 현재 col과 계산된 두 대각선 ID가 이미 사용 중이라면, 해당 col은 유효하지 않으므로 다음 col로 넘어갑니다. (가지치기)
  • 퀸을 놓는 것처럼 해당 col, d1, d2를 true로 표시합니다.
  • dfs(row + 1): 다음 행으로 재귀 호출합니다.
  • used... = false;: 재귀 호출이 끝나면(백트래킹), 상태를 원래대로 복구하여 다른 경우의 수를 탐색할 수 있도록 합니다.

이해한 내용

• 보드 시뮬레이션 → 상태 공간 탐색: N-Queen은 체스판 위에서 퀸을 옮기는 시뮬레이션이 아니라, 가능한 모든 배치를 탐색하는 상태 공간 탐색 문제임을 명확히 이해했습니다.
• 대각선의 수학적 정의: row - col과 row + col이 어떻게 대각선을 나타내는지를 좌표계와 함께 그림으로 머릿속에 그릴 수 있게 되었습니다. 이는 기하학적 직관과 수학적 정의를 연결하는 중요한 순간이었습니다.
• 백트래킹의 작동 원리: for 루프를 통한 선택(분기), if 조건문에서의 가지치기, 재귀 호출(깊이 이동), 그리고 상태 복구를 통한 복귀(백트래킹)의 전체적인 흐름을 명확히 이해했습니다. 실패 시에는 continue 또는 for 루프의 종료를 통해 암묵적으로 복귀한다는 사실도 알게 되었습니다.

실전 적용

이번 학습 내용을 바탕으로 다음과 같은 실전 적용을 계획하고 있습니다.

• 코드 직접 구현: ChatGPT가 제공한 정석 코드를 직접 타이핑하고 실행하면서 디버깅하는 과정을 통해 각 라인의 역할을 더 확실히 체득할 것입니다.
• 다른 백트래킹 문제 적용: 스도쿠, 조합 문제 등 다른 백트래킹 문제에도 동일한 dfs(상태) → 선택 → 제약 확인 → 다음 상태 → 복구 패턴을 적용해보는 연습을 할 것입니다.
• 성능 최적화 탐구: 비트마스크를 이용한 최적화나 대칭성을 이용한 탐색 공간 축소 등 N-Queen 문제의 성능을 더욱 향상시키는 방법에 대해서도 학습할 계획입니다.

추가 학습 계획

• 비트마스크 N-Queen: bool 배열 대신 비트 연산을 활용하여 N-Queen을 구현하고 속도 차이를 비교해보고 싶습니다.
• 대칭성 제거: N-Queen 문제에서 대칭성을 이용해 탐색 공간을 절반으로 줄이는 방법에 대해 더 깊이 공부하고 싶습니다.
• 다른 제약 만족 문제(CSP) 탐구: N-Queen과 유사한 구조를 가진 스도쿠, 라틴 스퀘어 등의 문제를 백트래킹으로 풀어보며 알고리즘의 범용성을 익힐 것입니다.

참고 자료

• ChatGPT와의 대화 내용: N-Queen 문제에 대한 질문과 답변 전체
• BOJ 9663 (N-Queen): 문제 해결을 위한 실제 구현 기준 및 제약 조건 확인