[코드트리 후기] Backtracking 이해하기

백트래킹 (Backtracking)

 

어릴 적 신문 신문 한 구석에 있던 "미로 찾기"를 떠올려 보세요. 갈림길을 만나면 일단 한 곳으로 가봅니다. 가다 보니 막다른 길이 나오면 어떻게 하나요? 다시 직전 갈림길로 되돌아가서 다른 길을 선택하죠?

알고리즘에서 이 되돌리기 전략을 백트래킹이라고 부릅니다. 백트래킹은 모든 경로를 다 가보되 지금 선택한 길이 정답이 될 가능성이 있는 지 체크합니다. 이를 알고리즘 용어로 유망성 검사(Promising)이라고 합니다. 그리고 그 길이 "아, 이 길은 가봐야 어차피 답이 안 나오겠네?"라는 생각이 드는 순간 그 경로를 과감히 포기하고 직전 단계로 돌아갑니다. 이 스마트한 포기 과정을 알고리즘 용어로 가지치기(Pruning)라고 부릅니다.

 

즉, 백트래킹은 재귀적으로 탐색하다가 답이 안될 것 같으면 이전으로 돌아가서 다른 길을 찾는 알고리즘입니다.

 

예제

1부터 K까지의 숫자가 적힌 카드가 있습니다. 이 카드 주머니에서 한 장을 뽑아 기록하고, 다시 주머니에 넣은 뒤(중복 허용) 총 N번을 뽑아 만들 수 있는 모든 숫자의 조합을 사전순으로 출력하는 문제입니다.

 

#include <iostream>
#include <vector>

using namespace std;

int K, N;
vector<int> path; // 현재까지 고른 숫자들을 담을 바구니

// 백트래킹 함수
void select_cards(int depth) {
    
    // 1. 탈출 조건 : N개의 숫자를 모두 골랐다면 출력하고 퇴각!
    if (depth == N) {
        for (int i = 0; i < N; i++) {
            cout << path[i] << " ";
        }
        cout << "\n";
        return; 
    }

    // 2. 가지치기 및 탐색: 1부터 K까지의 숫자를 하나씩 시도
    for (int i = 1; i <= K; i++) {
        
        path.push_back(i);      // [선택] i번 숫자를 바구니에 담는다
        
        select_cards(depth + 1); // [진입] 다음 숫자를 고르러 한 단계 더 깊이!
        
        path.pop_back();        // [취소] 되돌아왔으니 방금 담은 숫자를 빼낸다 (Ctrl + Z)
    }
}

int main() {
    cin >> K >> N;

    select_cards(0); 

    return 0;
}

 

 

백트래킹 기본 구조 (C++)

#include <iostream>
#include <vector>

using namespace std;

// 전역 변수 선언: 상태를 기록
vector<int> path;

// 백트래킹 함수
void backtrack(int depth) {
    // 1: 탈출 조건
    if (조건을_만족했는가(depth)) {
		...
        return; // return하여 이전 단계로 되돌아감
    }

    // 2: 가지치기 및 탐색
    for (int next_candidate = 1; next_candidate <= 후보_개수; next_candidate++) {
        
        // 유망성 검사: 이 길로 계속 가도 안전한가? (가지치기)
        if (안전한가(next_candidate)) {
            
            // 1. [선택] 현재 상태를 기록
            visited[next_candidate] = true;
            path.push_back(next_candidate);

            // 2. [진입] 다음 단계로 더 깊이 탐색 (재귀 호출)
            backtrack(depth + 1);

            // 3. [취소] 퇴각! 직전 상태로 완벽하게 복원 (Ctrl + Z)
            path.pop_back();
            visited[next_candidate] = false;
        }
    }
}

int main() {
    backtrack(0);
    return 0;
}

 

 

🚨 자주 하는 실수

 

1. 탈출 조건 빼먹기

"정답을 찾았는 데도 계속 도는 재귀 호출(무한루프)"

백트래킹은 원하는 목표치에 도달하면 하던 일을 멈추고 위로 돌아가야 합니다.

 

2. 가지치기 및 탐색 과정에서 [취소] 빼먹기

백트래킹의 핵심은 갔다가 아니면 완벽하게 돌아온다입니다. 들어가는 것에만 신경 쓰고 돌아 나와서 흔적을 지우는 것을 까먹습니다.

 

 

 

 

 

 

코드트리 바로가기

Codetree: Master Coding Interviews - Data Structures & Algorithms