[Algorithm] 백트래킹 (Backtracking)

백트래킹을 처음 접했을 때는 단순히 모든 경우의 수를 탐색하는 깊이 우선 탐색(DFS)이라고 생각했지만, 학습을 통해 백트래킹의 진정한 힘은 '가지치기(Pruning)'에 있다는 것을 깨달았습니다. 하나의 패턴을 이해하고 나니 N-Queens나 스도쿠 같은 완전히 다른 문제들도 동일한 접근법으로 해결할 수 있다는 것을 알게 되어 응용할 수 있겠다는 자신감도 생겼고 앞으로는 어떤 조건을 '유망하다'고 판단하고 효율적으로 가지치기를 할 것인지 고민하는 것이 관건이 될 것 같습니다. 

---

백트래킹 (Backtracking)

백트래킹은 가능한 모든 경우의 수를 탐색하는 알고리즘입니다. 하지만 무작정 모든 경우의 수를 다 보는 부르트 포스(Brute Force)와는 달리, 조건에 맞지 않는 경로는 더 이상 탐색하지 않고 이전 단계로 되돌아가 다른 경로를 찾는 방식으로 탐색 효율을 높이는 방법입니다.

 

예를 들어 미로 찾기에서 한 갈림길에서 특정 길을 선택해 가다가 막다른 길을 만나면 마지막 갈림길로 되돌아가 다른 길을 선택하는 것과 똑같습니다. 주로 재귀 함수를 이용해 구현하며, '조건을 만족하는 모든 조합'을 찾아야 하는 문제에 효과적인 알고리즘입니다.

 

장점

• 불필요한 경로를 탐색하지 않아 브루트 포스보다 훨씬 효율적으로 탐색할 수 있습니다.
• 재귀적인 구조가 명확해 다양한 문제에 적용해 구현하기 용이합니다.

단점

• 가지치기를 거의 할 수 없는 문제의 경우, 모든 경우의 수를 다 탐색하게 되어 시간 복잡도(O(kN))을 가질 수 있습니다.
• 재귀 호출이 매우 깊어질 경우 스택 오버플로우가 발생할 수 있습니다.

---

코딩테스트 문제 풀어보기 - N과 M (1)

https://www.acmicpc.net/problem/15649

: 1부터 N까지 자연수 중에서 중복 없이 M개를 골라 만들 수 있는 수열을 모두 구하는 프로그램을 작성해 오름차순으로 출력하는 문제

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ');

const N = parseInt(input[0]);
const M = parseInt(input[1]);

function solution(N, M) {
    // 1부터 N까지의 숫자 배열 생성
    const numbers = Array.from({ length: N }, (_, i) => i + 1);
    // 방문 여부를 체크할 배열
    const visited = Array(N).fill(false);
    // 현재 수열을 저장할 배열
    const temp = [];
    // 최종 결과를 저장할 문자열
    let result = '';

    function backtrack(depth) {
        // 1. 재귀 탈출 조건: M개의 숫자를 모두 선택한 경우
        if (depth === M) {
            // 현재 만들어진 수열을 result에 추가하고 리턴
            result += temp.join(' ') + '\n';
            return;
        }

        // 2. 재귀 호출 (백트래킹 로직)
        for (let i = 0; i < N; i++) {
            // 아직 방문하지 않은 숫자라면
            if (!visited[i]) {
                // 1. 방문 처리 (선택)
                visited[i] = true;
                // 2. 현재 숫자를 수열에 추가
                temp.push(numbers[i]);
                
                // 3. 다음 깊이로 재귀 호출
                backtrack(depth + 1);
                
                // 4. 수열에서 마지막 숫자 제거 (백트래킹)
                temp.pop();
                // 5. 방문 처리 해제 (백트래킹) -> 다음 탐색을 위해 상태를 원상복구
                visited[i] = false;
            }
        }
    }

    // 깊이 0부터 탐색 시작
    backtrack(0);
    // 최종 결과 출력 (마지막 줄바꿈 제거)
    console.log(result.trim());
}

solution(N, M);

 

코드는 backtrack이라는 재귀 함수를 사용해 모든 숫자 조합을 탐색하고 있습니다. visited 배열을 사용해 숫자의 중복 사용을 방지하고, 수열의 길이가 M이 되면 result에 값을 추가하는 방식으로 동작합니다.

 

특히 코드에서 백트래킹 로직을 찾아보자면 다음과 같습니다.

for (let i = 0; i < N; i++) {
    if (!visited[i]) {
        // --- 1. 선택 (Choose) ---
        visited[i] = true;
        temp.push(numbers[i]);
        
        // --- 2. 탐색 (Explore) ---
        backtrack(depth + 1);
        
        // --- 3. 복구 (Un-choose / Backtrack) ---
        temp.pop();
        visited[i] = false;
    }
}

• for 루프는 1부터 N까지의 모든 숫자를 하나씩 확인하며 수열의 다음 자리에 들어갈 후보로 만듭니다.
• if (!visited[i])는 가지치기(Pruning) 부분입니다. 만약 i번째 숫자가 아직 사용되지 않았다면(visited[i] == false) 다음 단계를 진행하고, 이미 사용된 숫자라면 건너뜁니다.

① 선택 (Choose)

• visited[i] = true;: i번째 숫자를 사용하겠다고 방문 처리를 합니다.
• temp.push(numbers[i]);: 현재 수열(temp)에 i번째 숫자를 추가합니다.

② 탐색 (Explore)

• backtrack(depth + 1);: 현재 temp에 숫자가 하나 더 추가되었으므로 depth를 1 증가시켜 다음 자리의 숫자를 찾기 위해 재귀 호출을 합니다.

③ 복구 (Un-choose / Backtrack)

• 재귀 호출 backtrack(depth + 1)이 끝나고 리턴되면 이 부분으로 돌아옵니다. 이는 i번째 숫자로 시작하는 모든 수열을 다 찾았다는 의미입니다.
• temp.pop();: 다음 for 루프에서 다른 숫자를 탐색하기 위해, 방금 temp에 넣었던 숫자를 다시 빼냅니다.
• visited[i] = false;: i번째 숫자를 미방문 상태로 되돌립니다.
• 이 '복구' 과정이 있기 때문에, 예를 들어 [1, 2]를 탐색한 후에 [1, 3]을 탐색하는 것이 가능해집니다. 2를 빼고 방문 기록을 지워야 3을 새로 선택할 수 있기 때문입니다.

---

요약 정리하기

항목	설명	키워드
개념	모든 가능한 경우의 수를 탐색하되, 조건에 맞지 않는 경로는 포기하고 이전 단계로 되돌아가 다른 경로를 찾는 알고리즘	조합 탐색, 상태 공간 트리
핵심 구현 방법	가지치기 (Pruning): 해가 될 가능성이 없는(유망하지 않은) 경로는 더 이상 탐색하지 않고 잘라내어 탐색의 효율을 높입니다.	유망성 검사(Promising)
탐색 방식	깊이 우선 탐색 (DFS, Depth-First Search): 하나의 경로를 끝까지 탐색한 후, 이전 갈림길로 돌아와 다른 경로를 탐색하는 방식입니다.	DFS, 상태 트리
주요 구현	재귀 함수 (Recursion): 현재 상태에서 다음 상태를 호출하는 재귀적인 구조로 구현하는 것이 가장 일반적이고 직관적입니다.	재귀, 스택(Stack)
장점	불필요한 탐색을 줄여 단순한 브루트 포스(Brute-force)보다 훨씬 효율적입니다. 구조가 명확해 다양한 문제에 적용하기 쉽습니다.	최적화된 탐색, 범용성
단점	최악의 경우 모든 경우를 탐색하게 되어 여전히 지수 시간 복잡도를 가질 수 있습니다. 재귀가 깊어지면 스택 오버플로우가 발생할 수 있습니다.	최악의 성능, 스택 오버플로우
대표 문제 유형	N-Queens, 스도쿠(Sudoku) 풀이, 미로 찾기, 순열/조합 생성 문제 (N과 M 시리즈) 등 모든 조합을 찾아야 하는 문제에 효과적입니다.	N-Queens, 순열, 조합
코드 구조	if (탈출 조건) → for (모든 선택지) → if (유망성 검사) → 선택 → 재귀 호출 → 선택 해제(복구)의 패턴을 가집니다.	선택 → 탐색 → 복구