개념 이해 단계: 백트래킹과 N-Queen
백트래킹 (Backtracking) 이란?
문제를 해결하기 위해 모든 가능성을 탐색하다가, 현재 경로가 정답이 될 수 없다고 판단되면 (유망하지 않으면) 즉시 이전 단계로 되돌아가서(Backtrack) 다른 경로를 탐색하는 알고리즘 기법입니다.
💡 핵심 포인트
- 상태 공간 트리(State Space Tree): 문제 해결 과정을 트리 형태로 구성하여 탐색합니다.
- 가지치기(Pruning): 정답이 될 가능성이 없는 노드(Node)는 더 이상 탐색하지 않고 잘라내어 탐색 시간을 대폭 줄입니다.
준비 단계: N-Queen 규칙 알아보기
체스 게임의 「여왕(Queen)」은 가장 강력한 말입니다. N-Queen 퍼즐의 3가지 핵심 규칙을 살펴볼까요?
1. 기본 구성
가로 N칸, 세로 N칸의 체스판에 N개의 퀸(Queen)을 배치해야 합니다.
2. 퀸의 파워
퀸은 가로, 세로, 대각선 방향으로 칸 수에 제한 없이 끝까지 이동하며 공격할 수 있습니다.
3. 최종 목표
어떤 퀸들도 서로 공격할 수 없도록, 즉 같은 행, 열, 대각선에 겹치지 않게 안전하게 배치하세요.
단계별 풀이: 4-Queen으로 익히기
탐색 트리를 따라가며 4-Queen 문제를 인공지능처럼 단계별로 풀어 봅시다.
첫 번째 줄에 첫 번째 퀸 놓기 (초기 상태에서 시작)
빈 체스판이 초기 상태입니다.
첫 번째 행, 첫 번째 열에 퀸을 놓습니다.
빨간색 칸은
첫 번째 퀸이 공격할 수 있는 범위입니다.
이제 다음 줄에는 저 칸들을 피해서 놓아야 합니다.
다음 줄에 두 번째, 세 번째 퀸 놓기 (경로 탐색)
공격받지 않는 위치를 찾아 두 번째 줄과 세 번째 줄에 차례대로 퀸을 배치해 봅니다. 이 과정이 바로 트리의 가지를 타고 내려가는 경로 탐색입니다.
막혔다면 뒤로 돌아가기 (백트래킹)
만약 세 번째 줄에 퀸을 놓으려고 보니, 어떤 칸에 놓아도 다른 퀸에게 공격받게 된다면 어떻게 해야 할까요?
인공지능은 그 길이 틀렸음을 알고 이전 단계(위쪽 가지)로 다시 돌아가서 퀸의 위치를 바꿉니다.
이렇게 되돌아가 다른 길을 탐색하는 것이 백트래킹입니다.
4개의 퀸을 모두 놓았다 (목표 상태 도달)
모든 경로를 체계적으로 탐색하다 보면 결국 4개의 퀸이 서로 공격하지 않는 배치도를 찾게 됩니다. 인공지능이 문제의 해답을 찾은 이 순간이 바로 목표 상태입니다.
헷갈리기 쉬운 점
「인공지능은 그냥 무작정 모든 경우의 수를 한 번씩 다 해 보는 거 아니야?」
완전탐색 (다 놓고 나서 확인)
「각 줄에 하나씩 일단 다 놓아 본 다음, 완성된 배치를 하나하나 규칙에 맞는지 확인하자.」
8×8이라면 8을 여덟 번 곱한 16,777,216가지를 전부 만들어 봐야 합니다.
백트래킹 (한 칸 놓을 때마다 확인)
「이 칸은 벌써 공격받네? 그럼 여기서 뻗어 나가는 배치는 아예 만들지 말고
통째로 잘라 버리자(가지치기).」
백트래킹도 가능성을 빠짐없이 살펴보기 때문에 답이 있으면 반드시 찾아냅니다.
「N-Queen 실습하기」에서 8×8을 실행해 보면 첫 답을 찾을 때까지 검사한 칸이
[방문] 876칸에서 멈춥니다.
둘 다 빠짐없이 본다는 점은 같습니다. 다른 것은 언제 확인하느냐입니다 — 다 놓은 뒤에 확인하면 완전탐색, 한 칸 놓을 때마다 확인해서 가망 없는 가지를 그 자리에서 잘라 내면 백트래킹입니다.
직접 해 보기: 퀸을 배치해 보세요
체스판을 직접 클릭해서 퀸을 배치해 보세요.
셀을 클릭하면 퀸이 배치/제거됩니다. 같은 행·열·대각선에 퀸이 겹치면 빨간색으로 충돌을 알려 줍니다. N개의 퀸을 충돌 없이 배치하면 성공입니다.
배치 현황
목표: 8개 모두 배치 + 충돌 없음
충돌 위치
충돌 조건
- ↔ 같은 행(가로)에 2개 이상
- ↕ 같은 열(세로)에 2개 이상
- ✕ 같은 대각선에 2개 이상
셀에 마우스를 올리면 공격 범위가 표시됩니다.
실습 단계: N-Queen 실습하기
상태 공간 트리
AI 탐색을 시작하면 이곳에
전체 트리 구조가 그려집니다.
트리 화면 조작법
탐색 트리는 마우스로 드래그하여 이동하거나 휠을 굴려 확대/축소할 수 있습니다.
손으로 조작하면 보기 방식이 「자유 이동」으로 바뀝니다.
AI가 어디를 탐색하는지 따라가려면 보기 방식을 「노드 추적 (추천)」으로 두세요.
마무리 단계: 코드로 보는 원리
코드로 보는 DFS와 백트래킹 원리
「N-Queen 실습하기」에서 그려진 트리의 노드 하나는 아래 파이썬 코드의 for 반복 한 번,
곧 「이 칸에 놓아도 될까?」 하고 검사한 칸 하나에 해당합니다.
is_safe를 통과해 퀸을 놓으면 재귀 호출(Recursive Call)이 일어나
트리가 아래로(자식 노드, Child) 깊어지고, 통과하지 못하면 그 칸은 가지치기되어
옆 칸(형제 노드)으로 넘어갑니다.
한 줄의 열을 끝까지 다 써 보고도 답이 없어 return False를 만났을 때 비로소
위로(부모 노드, Parent) 되돌아옵니다 — 이것이 백트래킹입니다.
# DFS(깊이 우선 탐색)를 이용한 N-Queen 백트래킹
def solve_n_queens(row, n, state):
if row == n:
return True # 트리 끝단 도달 정답을 찾음
for col in range(n):
# 1. 시도 (Try) 및 가지치기(Pruning) 검사
if is_safe(row, col, state):
state[row] = col # 안전하다면 퀸을 배치 (Place)
# 2. 다음 줄(depth) 탐색을 위해 재귀 호출 (자식 노드로 이동)
if solve_n_queens(row + 1, n, state):
return True
# 3. 백트래킹 (Backtracking)
# 자식 노드에서 답을 못 찾고 돌아왔으므로 상태를 복구하고 다른 칸 시도
state[row] = -1
return False # 이 노드의 모든 자식 경로에 답이 없음