백트래킹

언제 쓰나

“가능한 경우를 전부 만들어 봐야 하는” 문제에서 씁니다. 문제에서 이런 신호가 보이면 백트래킹을 먼저 떠올려 보세요.

• 모든 경우를 나열하라고 합니다. [1, 2, 3]을 늘어놓는 모든 순서(순열), 몇 개를 고르는 모든 방법(조합), 모든 부분집합 같은 것입니다.
• 하나를 고르면 다음에 고를 수 있는 것이 줄어듭니다. 순열에서 1을 첫 자리에 쓰면, 남은 자리에는 1을 다시 쓸 수 없습니다.
• 입력이 작습니다. 경우의 수가 빠르게 늘어나기 때문에(3개면 6가지, 10개면 약 360만 가지) 보통 n이 10 안팎일 때 씁니다.

어떻게 동작하나

손으로 순열을 만들어 보면

[1, 2, 3]의 순열을 종이에 직접 적는다고 생각해 보겠습니다.

1. 첫 자리에 1, 둘째 자리에 2, 셋째 자리에 3을 놓습니다. [1, 2, 3] 하나 완성입니다.
2. 셋째 자리에 다른 수를 넣어 보고 싶지만 남은 수가 없습니다. 그래서 한 걸음 물러나 둘째 자리로 돌아갑니다.
3. 둘째 자리의 2를 빼고 3을 넣습니다. 그러면 셋째 자리에는 남은 2가 들어가 [1, 3, 2]가 됩니다.
4. 1로 시작하는 경우를 다 만들었으면 첫 자리로 돌아가, 2로 시작하는 경우를 같은 순서로 만듭니다.

위 순서처럼 수를 골라 보다가 더 고를 것이 없으면 앞 자리로 돌아가 다른 수를 넣어 보는 방식을 백트래킹(backtracking)이라고 부릅니다. 왔던 길(track)을 되짚어(back) 간다는 뜻입니다.

그림으로 그리면 나무가 됩니다

위 과정을 그림으로 옮기면 아래로 가지를 뻗는 나무 모양이 됩니다. 이 그림을 상태 공간 트리라고 부르는데, 읽는 법은 이렇습니다.

• 맨 위 [ ]는 아직 아무것도 고르지 않은 상태입니다.
• 한 칸 아래로 내려갈 때마다 수를 하나 고른 것입니다.
• 맨 아래 칸에 닿으면 세 자리를 다 채운 것, 즉 순열 하나가 완성된 것입니다. [1, 2, 3]이면 맨 아래 칸이 6개이고, 이것이 순열 6개입니다.

백트래킹은 이 나무에서 한 줄기를 맨 아래까지 먼저 내려갑니다. 맨 아래에 닿으면 한 칸 올라와 바로 옆 가지로 넘어갑니다.

코드에서는 두 변수가 이 움직임을 기억합니다.

• path: 지금까지 고른 수들. 나무에서 맨 위부터 지금 위치까지 내려온 길과 같습니다.
• used: 어떤 수를 이미 썼는지 표시하는 체크리스트. used[0]이 true면 1은 이미 쓰는 중입니다.

한 칸 올라올 때는 방금 고른 수를 되돌려야 합니다. path에서 그 수를 빼고 used도 false로 바꿔 두어야, 옆 가지로 넘어갔을 때 그 수를 다시 쓸 수 있습니다.

직접 따라가 보기

“다음”을 누르면 한 걸음씩 진행합니다. 4번째 단계에서 [1, 2, 3]이 완성되고, 5번째 단계에서 위로 올라옵니다. 이때 변수 칸의 path에서 3과 2가 빠지고 used가 다시 false로 바뀌는 것을 보세요.

되돌린다 되돌리지 않는다

처음부터 이전 자동 재생 다음

단계 1 / 22

상태 공간 트리 · nums = [1, 2, 3]

변수

path

[]

used

[, false, false, false]

result 0

아직 아무것도 고르지 않은 맨 위에서 시작합니다. "다음"을 눌러 보세요

• 지금 위치
• 지금까지 고른 길 (path)
• 완성된 순열
• 아직 안 가 본 곳

위쪽에서 “되돌리지 않는다”를 고르면, 되돌리는 두 줄(path.pop(), used[i] = false)을 뺀 코드가 실행됩니다. 첫 순열 [1, 2, 3]을 만든 뒤 위로는 올라오지만, 1·2·3이 모두 “쓰는 중”으로 남아 있어서 더는 아무것도 고를 수 없습니다. 그래서 순열 하나만 만들고 끝납니다.

대표 문제 풀이

LeetCode 46은 서로 다른 수가 담긴 배열 nums를 받아, 가능한 모든 순서를 돌려주는 문제입니다. 예를 들어 nums = [1, 2, 3]이면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]을 돌려주면 됩니다.

var permute = function (nums) {
  const result = []; // 완성된 순열을 모으는 곳
  const path = []; // 지금까지 고른 수
  const used = new Array(nums.length).fill(false); // 이미 쓴 수 표시

  function backtrack() {
    // 모든 자리를 채웠다면 순열 하나 완성
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // 이미 쓴 수는 건너뛴다

      used[i] = true; // ① 고른다
      path.push(nums[i]);

      backtrack(); // ② 이어서 다음 자리를 채운다

      path.pop(); // ③ 되돌린다
      used[i] = false;
    }
  }

  backtrack();
  return result;
};

반복문 안은 ① 고르기, ② 다음 자리 채우기, ③ 되돌리기 순서로 흘러갑니다. 나무 그림에 대면 ①에서 한 칸 내려가고, ②에서 그 아래를 끝까지 둘러본 뒤, ③에서 한 칸 올라옵니다.

완성된 순열을 담을 때 path를 그대로 넣지 않고 [...path]로 복사하는 것은, path가 모든 가지가 함께 쓰는 배열 하나이기 때문입니다. 복사하지 않고 넣으면 나중에 pop으로 수를 뺄 때 이미 담아 둔 결과에서도 수가 같이 빠집니다.

실행 시간은 O(n · n!)입니다. 순열이 n!개이고, 하나를 담을 때마다 길이 n짜리 배열을 복사하기 때문입니다. 결과를 담는 공간을 빼면 path, used, 재귀 깊이가 모두 n을 넘지 않으므로 추가 공간은 O(n)입니다.

자주 하는 실수

되돌릴 것을 하나만 되돌립니다. 저는 처음에 “쓴 수를 다시 쓸 수 있게 used만 돌려놓으면 된다”고 생각했고, path.pop()을 빠뜨렸습니다. 수를 고를 때 used[i]와 path를 함께 바꿨으니, 되돌릴 때도 둘 다 되돌려야 합니다.

빠뜨리지 않으려면 ①과 ③을 나란히 놓고, ①에서 바꾼 줄마다 ③에 짝이 되는 줄이 있는지 확인하면 됩니다.