https://www.codetree.ai/ko/trails/complete/dashboard/intermediate-low
Codetree: Master Coding Interviews - Data Structures & Algorithms
Master algorithms, ace tech interviews, and elevate your coding skills with Codetree's systematic curriculum and expert-crafted problem sets.
www.codetree.ai
백트래킹을 처음 접했을 때, 단순히 '모든 경우를 다 해보는 것(Brute-force)'과 무엇이 다른지 혼란스러웠다. 하지만 공부를 거듭하며 깨달은 것은, 백트래킹은 단순히 다 해보는 것이 아니라 "아닌 것 같은 길은 과감히 버리고(Pruning), 올바른 해답을 찾아 나가는 현명한 되돌아오기"라는 점이다.
1. 백트래킹, 나만의 쉬운 정의
백트래킹은 미로 찾기와 같다. 갈림길에서 한쪽 길을 선택해 끝까지 가보고, 막다른 길이라면 다시 이전 갈림길로 돌아와 다른 길을 탐색한다. 이때 중요한 것은 유망성(Promising)을 판단하는 것이다. "지금 내가 선택한 경로가 답이 될 가능성이 있는가?"를 끊임없이 스스로에게 묻고, 가능성이 없다면(Pruning) 즉시 그 가지를 쳐내어 시간을 절약하는 것이 핵심이다.
2. 코드트리 문제 풀이: 핵심 로직과 구현
백트래킹은 재귀(Recursion) 함수와 떼려야 뗄 수 없는 관계다. 상태를 기록할 visited 배열과 현재 단계 depth를 매개변수로 넘겨주며 정답을 찾아간다.
[핵심 로직]
- 기저 조건(Base Case): 원하는 깊이(또는 조건)에 도달했는지 확인하고 결과 저장.
- 반복문/재귀: 가능한 모든 선택지를 시도.
- 백트래킹(Backtracking): 선택했던 값을 다시 되돌려 놓아(원상복구), 다음 탐색에 영향이 없도록 함.
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> path;
bool visited[10]; // 방문 여부 체크
void backtrack(int depth) {
// 기저 조건: 원하는 길이에 도달했을 때
if (depth == n) {
for (int x : path) cout << x << " ";
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
// 선택
visited[i] = true;
path.push_back(i);
// 다음 단계로
backtrack(depth + 1);
// 백트래킹: 상태 원상복구 (가장 중요한 부분!)
path.pop_back();
visited[i] = false;
}
}
}
int main() {
cin >> n;
backtrack(0);
return 0;
}
3. 시행착오와 꿀팁
백트래킹을 구현하다 보면 '무한 루프'나 '잘못된 결과'를 마주하기 쉽다. 내가 시행착오를 겪으며 깨달은 점들이다.
- 자주 하는 실수: 백트래킹을 수행한 후 visited[i] = false;를 빼먹는 경우다. 이 한 줄이 없으면 다시는 그 숫자를 사용할 수 없어 전체 경우의 수를 탐색하지 못한다.
- 헷갈리기 쉬운 함정: 문제에서 요구하는 '순열(Permutation)'인지 '조합(Combination)'인지 명확히 구분해야 한다. 조합이라면 재귀 호출 시 현재 인덱스 이후의 값만 확인하도록 파라미터를 넘겨야 중복을 방지할 수 있다.
- 구현 꿀팁: path 벡터를 전역으로 쓰거나 참조자(&)로 넘기면 메모리 오버헤드를 줄일 수 있다. 또, 가지치기(Pruning) 조건이 명확할수록 코드의 성능은 기하급수적으로 빨라진다. 조건을 최대한 촘촘히 세우는 연습이 필요하다.
함수 문제 때 느꼈던 것처럼, 처음에는 막막했던 재귀 구조가 이제는 조금씩 손에 익기 시작했다. 백트래킹 또한 처음에는 이해가 안 가더니, 여러 문제를 풀어보며 '상태를 저장하고 원상복구하는 패턴'이 눈에 들어오기 시작했다. 이렇게 하나씩 기본기를 견고하게 다져나가다 보면, 언젠가 더 어려운 DP(동적 계획법)나 그래프 심화 문제도 자연스럽게 정복할 수 있을 것 같다는 기분 좋은 자신감이 든다.