Backtracking, 백트래킹, JavaScript

 

Backtracking, 백트래킹

백트래킹이란?

백트래킹은 DFS (깊이 우선 탐색) 의 한 형태로, 모든 후보 해를 탐색하되, 해답이 될 수 없는 부분은 미리 가지치기하여 탐색 범위를 줄이는 기법입니다. 

 

예를 들어, 특정 조건을 만족해야 하는 조합, 순열, 그래프의 경로 문제에서 자주 활용됩니다.

핵심 아이디어는 다음과 같습니다:

1. 해단 노드(상태)가 유효한지 검사한다.
2. 만약 유효하지 않다면(조건을 만족하지 않는다면) 바로 백트래킹(Backtracking)하여 이전 단계로 돌아간다.
3. 유효하다면 다음 노드(상태)로 이동하여 탐색을 이어간다.
4. 목표 조건(해를 찾았는지 or 모든 후보를 탐색했는지) 달성 시까지 1~3번 과정을 반복한다.

 

핵심 개념과 동작 원리

상태(state)

• 상태는 현재까지 내린 결정(선택)들의 집합을 말함
• 예: N-Queen 문제에서 `board[row] = col`로 표현되는 퀸의 배치 위치

가지치기(pruning)

• 특정 상태가 추가 탐색을 진행해도 해가 될 가능성이 전혀 없는 경우, 바로 탐색을 중단(백트래킹)하고 이전 단계로 돌아가는 것
• 예: 퀸이 이미 서로를 공격할 수 있는 위치라면, 더 이상 놓을 자리가 없는 경우 등

깊이 우선 탐색(DFS)과 백트래킹

• 백트래킹은 DFS 형태로 진행되지만, 유망(promising)하지 않은 경로를 빠르게 배제하는 기법을 포함함
• 결과적으로, 최악의 경우 모든 노드를 탐색하지만, 가지치기가 훌륭히 작동한다면 탐색 범위를 크게 줄일 수 있음

지수적 복잡도

• 최악의 경우 여전히 O(N!), O(2^N) 등 지수 시간이 소요될 수 있음. 다만, 프루닝(pruning)을 잘 적용하면 실제 연산량이 크게 감소할 수 있음

 

대표적인 활용 분야

퍼즐 & 게임

• 예: N-Queen, Sudoku, 미로 찾기, 아홉 칸 퍼즐 등
• 해당 문제들은 여러 제약 조건이 있어, 특정 경로가 유망하지 않으면 빠르게 배제할 수 있음

조합론적 문제(순열, 조합, 부분 집합)

• 순열(Permutation) 생성, 조합(Combination) 찾기, 부분 집합(Subset) 구하기 등
• 모든 경우의 수를 탐색하되, 중간 단계에서 유망하지 않은 부분을 건너뛸 수 있음

그래프 탐색

• Hamiltonian Path, Hamiltonian Cycle, DFS 변형 문제 등
• 방문 순서, 경로 구성 등을 제한하는 조건이 있을 때 적절히 가지치기를 적용함

 

효과적인 상황

제약 조건이 명확할 때

• 예: 두 원소 간의 충돌 여부, 이미 사용한 원소 목록, 현재까지의 비용 등
• 어떤 조건이라면 더 이상 탐색해도 소용없다라는 명확한 규칙이 있을 수록 백트래킹이 효과적

결과의 수가 지수적으로 증가하지만, 실제로는 제한되는 경우

• 이론상 `N!` 혹은 `2^N`이지만, 문제 특성상 중간에 많이 잘려나가는 경우가 많을 때 좋은 성능을 발휘함.

최적해(optimal) 대신 정답(feasible) 검증이 중요한 문제

• 특정 조건을 만족하는 배치(placement), 경로(path), 조합 등을 찾아야 할 때
• 단순히 정답 여부 또는 모든 해답을 나열하는 데 용이함

 

주의 사항

재귀 스택 한계

자바스크립트의 경우 함수 호출 스택에 제한이 있으므로, 문제 크기가 너무 크면 반복문 + 스택을 통한 DFS 접근이 필요할 수 있습니다.

과도한 중첩

백트래킹 로직을 구현할 때, 가지치기 조건이 복잡해질수록 코드 가독성이 떨어집니다.

또한, 상태 확인 함수와 재귀 함수를 분리하는 등 코드 구조를 명확히 유지해야 합니다.

중복 처리

순열/조합에서 같은 값을 여러 번 처리할 때, 중복 제거 로직을 넣지 않으면 쓸데없는 경우의 수가 엄청나게 늘어납니다.

무한 루프 주의

재귀 호출이 이어지는 과정에서, 상태를 복원(pop), 방문 처리를 적절히 해주지 않으면 무한 루프에 빠질 수 있습니다.

 

---

기본 구현

코드 예제: 배열의 모든 순열 구하기

function getPermutations(arr) {
  // 결과를 저장할 배열
  const results = [];

  // 백트래킹 함수: current는 현재까지 구성한 순열, remaining은 아직 선택하지 않은 요소들
  function backtrack(current, remaining) {
    // 만약 남은 요소가 없으면 순열 하나가 완성된 것이므로 결과에 저장
    if (remaining.length === 0) {
      results.push([...current]); // 복사본을 저장
      return;
    }
    // 남은 요소들 각각에 대해 선택 후 다음 단계 재귀 호출
    for (let i = 0; i < remaining.length; i++) {
      // 하나의 후보 선택
      current.push(remaining[i]);

      // 현재 선택한 요소를 제외한 나머지 배열 생성
      const nextRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));

      // 재귀 호출로 다음 단계 탐색
      backtrack(current, nextRemaining);

      // backtracking: 마지막에 선택한 요소를 취소하여 이전 상태로 복원
      current.pop();
    }
  }

  // 초기 상태: 빈 순열과 전체 배열이 남은 후보
  backtrack([], arr);
  return results;
}

// 사용 예: [1, 2, 3] 의 모든 순열 구하기
const permutations = getPermutations([1, 2, 3]);
console.log(permutations);

 

코드 설명

• getPermutations 함수:
  입력 배열을 받아 가능한 모든 순열을 생성합니다.
• backtrack 함수:
  • current: 현재까지 선택한 요소들을 담은 배열입니다.
  • remaining: 아직 선택하지 않은 요소들을 담은 배열입니다.
  • 재귀적으로 각 단계에서 하나의 요소를 선택한 후, 남은 요소들로 다시 호출합니다.
  • 만약 remaining이 빈 배열이면 순열이 완성된 것이므로 복사하여 results에 저장합니다.
• current.push(remaining[i]) 와 current.pop():
  이 부분이 백트래킹 핵심입니다. 재귀 호출 전에는 후보 요소를 선택(탐색)하고, 호출 후에는 선택한 요소를 제거(되돌리기)하여 다음 후보를 탐색할 수 있도록 합니다.