백트래킹
백트래킹(Backtracking)은 가능한 선택을 하나씩 시도하다가, 막다른 길임이 확인되면 즉시 되돌아가 다른 선택을 시도하는 탐색 기법입니다. algo-04(BFS/DFS)의 DFS와 원리가 비슷하지만, "이 갈래가 가망 없다"고 판단되는 순간 더 깊이 들어가지 않고 바로 포기(가지치기)한다는 점이 다릅니다.
핵심 개념
N-Queens 문제
N×N 체스판에 퀸 N개를 서로 공격하지 못하게(같은 행·열·대각선에 있지 않게) 배치하는 문제입니다. 이 시각화는 4×4 보드, 4개의 퀸으로 진행합니다.
핵심 개념
한 행씩 채워나가기
각 행에 퀸을 하나씩, 왼쪽 열부터 순서대로 시도합니다. 이전 행의 퀸들과 충돌하지 않는 첫 번째 열을 찾으면 그 자리에 놓고 다음 행으로 넘어갑니다.
핵심 개념
가지치기(Pruning)
어떤 행에서 안전한 열이 하나도 없으면, 그 아래로는 답이 나올 수 없다는 뜻입니다. 더 내려가지 않고 즉시 포기하는 것이 가지치기이며, 이것이 완전탐색보다 백트래킹이 빠른 이유입니다.
핵심 개념
되돌아가기(Backtrack)
막히면 방금 놓은 퀸을 치우고 이전 행으로 돌아가, 그 행에서 아직 시도하지 않은 다음 열을 시도합니다. 이전 행의 열도 다 시도했다면 한 단계 더 위로 돌아갑니다.
핵심 개념
탐색 트리
각 시도를 노드로, 다음 행으로의 진행을 간선으로 그리면 탐색 전체가 나무 모양이 됩니다. 막다른 가지는 잘려나가고(가지치기), 해로 이어지는 가지만 뿌리부터 끝까지 살아남습니다.
핵심 개념
완전탐색과의 차이
모든 배치(4⁴=256가지)를 다 확인하는 대신, 충돌이 확인되는 즉시 그 갈래를 포기하므로 실제로 확인하는 경우의 수가 훨씬 적습니다. 이 시각화에서는 22개의 탐색 노드만으로 모든 해를 찾습니다.
N-Queens의 유래
N-Queens는 체스판에서 퀸 N개를 서로 공격하지 못하게 놓는 문제입니다. 8×8 보드의 8-퀸 문제는 19세기 중반(1848년 막스 베젤의 제안)부터 알려진 퍼즐로 소개되고, 해가 모두 92개라고 알려져 있습니다. 백트래킹은 이런 '여러 선택을 이어 붙이는' 문제를 푸는 대표적인 방법입니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
백트래킹과 완전탐색의 차이는 무엇인가요?
완전탐색은 가능한 모든 경우를 끝까지 만든 뒤 확인합니다. 백트래킹은 선택을 하나씩 쌓으면서 조건을 어기는 순간 그 갈래를 버려, 확인하는 경우의 수를 줄입니다.
면접 질문
N-Queens에서 충돌 검사를 어떻게 빠르게 하나요?
열과 두 방향의 대각선을 각각 배열이나 집합으로 기록해 두면 새 퀸의 충돌 여부를 이전 퀸 전부를 훑지 않고 상수 시간에 확인할 수 있습니다(행 − 열은 음수가 될 수 있어서 N − 1을 더해 인덱스로 씁니다).
면접 질문
백트래킹의 시간 복잡도는 어떻게 되나요?
가지치기가 거의 안 되면 전수 탐색과 같아져 후보의 수(N!이나 Nᴺ 수준)에 가깝고, 가지치기가 잘 되면 줄지만 일반적인 상한은 보장하지 못합니다. 문제와 가지치기의 질에 따라 달라집니다.
면접 질문
백트래킹을 쓰는 다른 문제에는 무엇이 있나요?
스도쿠처럼 제약을 만족하는 배치를 찾는 문제가 대표적이고, 순열이나 부분집합 생성, 합이 정해진 조합 찾기도 같은 틀로 풀 수 있습니다.
실제 시스템에서는
함께 보면 좋은 토픽
참고 자료
Java — N-Queens 백트래킹
/* ── 한 행씩 채우다가, 막히면 되돌아감(재귀 + 원상복구) ────── */ public boolean solve(int[] cols, int row, int n) { if (row == n) return true; // 모든 행에 퀸을 놓았다 — 해 발견 for (int col = 0; col < n; col++) { if (isSafe(cols, row, col)) { cols[row] = col; // 일단 놓아본다 if (solve(cols, row + 1, n)) return true; // 다음 행 진행 cols[row] = -1; // 실패했다면 원상복구(백트랙) } } return false; // 이 행에서 안전한 열이 하나도 없음 — 가지치기 }
cols[row] = -1 한 줄이 백트래킹의 핵심입니다 — 재귀 호출이 실패로 끝나면, 방금 놓은 퀸을 반드시 치워야 다음 열을 공정하게 시도할 수 있습니다.
for문이 끝까지 돌았는데도 안전한 열을 못 찾았다면 false를 반환합니다 — 이 값이 호출한 쪽(이전 행)에 "이 갈래는 안 된다"는 신호가 되어 자연스럽게 되돌아갑니다.
Java — 충돌 검사 (isSafe)
/* ── 이미 놓은 퀸들과 같은 열/대각선인지 확인 ──────────────── */ public boolean isSafe(int[] cols, int row, int col) { for (int r = 0; r < row; r++) { // 이전 행들과만 비교하면 충분 (아래 행은 아직 비어 있음) int c = cols[r]; if (c == col) return false; // 같은 열 if (Math.abs(c - col) == Math.abs(r - row)) return false; // 같은 대각선 } return true; }
행은 이미 한 행에 퀸을 하나만 놓기로 정했으니 따로 검사할 필요가 없고, 열이 같은지와 대각선인지만 확인하면 됩니다.
두 칸이 대각선 위에 있다는 것은 |행 차이| == |열 차이|라는 뜻입니다 — 이 한 줄로 왼쪽 대각선과 오른쪽 대각선을 동시에 검사합니다.
Java — 모든 해 찾기 (되돌아가서 계속 탐색)
/* ── 해를 찾아도 멈추지 않고 기록한 뒤 계속 탐색 ──────────── */ public void solveAll(int[] cols, int row, int n, List<int[]> solutions) { if (row == n) { solutions.add(cols.clone()); // 해를 기록만 하고 return으로 끝내지 않음 return; } for (int col = 0; col < n; col++) { if (isSafe(cols, row, col)) { cols[row] = col; solveAll(cols, row + 1, n, solutions); // 성공/실패 여부와 상관없이 항상 진행 cols[row] = -1; // 해를 찾았어도 원상복구하고 다음 열 계속 시도 } } }
첫 번째 코드는 해를 하나만 찾으면 true를 반환하며 즉시 멈추지만, 이 버전은 해를 찾아도 계속 진행해 4-Queens의 두 해([1,3,0,2]와 [2,0,3,1])를 모두 찾습니다.
이 시각화의 "탐색 트리" 탭이 정확히 이 버전으로 동작합니다 — 첫 해를 찾은 뒤에도 트리 탐색이 끝까지 계속되는 것을 확인할 수 있습니다.
Q1
백트래킹(Backtracking)의 기본 동작 방식은?
Q2
4-Queens 문제에서 백트래킹이 탐색을 줄이는 방법은?
Q3
백트래킹에서 '치우기(remove)' 단계가 필요한 이유는?