백트래킹

🎯 학습 목표

이 강을 마치면 백트래킹을 선택 → 탐색 → 되돌리기의 표준 틀로 구현할 수 있습니다. 그리고 가지치기 조건을 설계해 탐색 공간을 줄이고, N-퀸·부분집합·조합 문제를 직접 풀 수 있게 됩니다.

15강의 완전 탐색은 모두 만든 뒤 거르는 방식이었습니다. 백트래킹은 만드는 도중에 가망 없는 가지를 잘라내는 방식입니다. 이론상 최악은 같아도 실제 실행 시간이 극적으로 달라집니다.

💡 선택 → 탐색 → 되돌리기

백트래킹은 부분 해를 하나씩 쌓아 가다가, 더 진행해도 답이 될 수 없다고 판단되면 되돌아가는 탐색 방법입니다. 재귀(13강)로 구현합니다.

백트래킹의 표준 틀

  def backtrack(현재 상태):
      if 완성됐다:
          결과에 기록
          return

      for 선택 in 가능한 선택지:
          if 이 선택이 유효하지 않다:
              continue          ← 가지치기 ★
          현재 상태에 선택을 추가     (선택)
          backtrack(다음 상태)        (탐색)
          현재 상태에서 선택을 제거   (되돌리기) ★

  ▲ '되돌리기'가 백트래킹이라는 이름의 유래다

  탐색 트리와 가지치기

           시작
         /  |  \
        1   2   3
       / \      ...
      2   3
     /     \
    3       2      ← 잎에 도달하면 하나의 답

  가지치기가 없으면 : 모든 잎까지 내려간다
  가지치기가 있으면 :

           시작
         /  |  \
        1   2   3
       / \  ✂    ← "2로 시작하면 절대 답이 안 됨"을
      2   3         여기서 판단해 통째로 잘라낸다

  ▲ 잘라낸 가지 아래의 모든 경우가 한 번에 사라진다
    깊이가 깊을수록 절감 효과가 크다

  ▲ 완전 탐색과의 차이
    완전 탐색 : 다 만들고 나서 조건 확인
    백트래킹   : 만드는 중에 조건 확인 → 못 갈 길은 안 간다

📖 가지치기 조건 설계하기

백트래킹의 성능은 가지치기 조건의 질로 결정됩니다. 좋은 조건을 찾는 방법을 정리하겠습니다.

가지치기 유형	판단 내용	예
제약 위반	규칙을 이미 어겼다	퀸이 서로 공격 가능
초과	이미 한도를 넘었다	합이 목표를 초과
낙관적 한계	남은 것을 다 써도 못 미친다	남은 합 + 현재 < 목표
중복 제거	같은 답을 이미 만들었다	같은 값 건너뛰기
대칭성	거울상은 볼 필요 없다	첫 선택을 절반으로 제한

중복 제거 가지치기 (매우 자주 나온다)

  [1, 2, 2, 3] 에서 합이 5인 조합 찾기

  가지치기 없이 하면
   (2, 3) 이 두 번 나온다 — 첫 번째 2와 두 번째 2

  해법
   ① 먼저 정렬한다
   ② 같은 깊이에서 이전과 같은 값이면 건너뛴다

   for i in range(start, len(nums)):
       if i > start and nums[i] == nums[i-1]:
           continue          ← 같은 깊이의 중복만 차단

  ▲ 조건이 i > start 인 이유
    i == start 는 '이 깊이에서 처음 쓰는 값'이므로 허용해야 한다.
    그래야 (2, 2) 같은 조합이 살아남는다.

  ▲ 이 조건을 i > 0 으로 잘못 쓰면
    정답인 (2, 2) 까지 걸러 버린다. 흔한 버그다.

가지치기 조건을 만들 때는 "이 조건이 정답을 잘라내지는 않는가"를 반드시 검증해야 합니다. 성능을 올리려다 답을 놓치는 것이 최악입니다.

💻 실전 예제 — 조합 합과 N-퀸

def combination_sum(nums, target):
    """중복 없이 합이 target 인 조합 모두 찾기"""
    nums.sort()                       # 중복 제거와 가지치기의 전제
    result = []
    path = []

    def backtrack(start, remain):
        if remain == 0:               # 완성
            result.append(path[:])    # 사본을 저장  ★
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:      # 가지치기: 초과
                break                 # 정렬돼 있으니 뒤도 다 크다
            if i > start and nums[i] == nums[i - 1]:
                continue              # 가지치기: 같은 깊이 중복
            path.append(nums[i])              # 선택
            backtrack(i + 1, remain - nums[i])  # 탐색
            path.pop()                         # 되돌리기

    backtrack(0, target)
    return result


def solve_n_queens(n):
    """N-퀸: 서로 공격하지 않게 퀸 n개 놓기 → 해의 개수"""
    cols = set()                      # 사용 중인 열
    diag1 = set()                     # row - col 이 같으면 같은 대각선
    diag2 = set()                     # row + col 이 같으면 반대 대각선
    count = 0

    def backtrack(row):
        nonlocal count
        if row == n:                  # 마지막 행까지 놓았다
            count += 1
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue              # 가지치기: 공격당함
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            cols.remove(col)          # 되돌리기
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return count


print(combination_sum([1, 2, 2, 3], 5))   # [[1, 2, 2], [2, 3]]
print(solve_n_queens(8))                   # 92

코드를 줄 단위로 보겠습니다.

• result.append(path[:]) — path가 아니라 사본을 저장합니다. path는 계속 바뀌므로 그대로 넣으면 나중에 전부 같은 값이 되는 유명한 버그가 납니다.
• if nums[i] > remain: break — 정렬돼 있으므로 지금 값이 크면 뒤는 모두 큽니다. continue가 아니라 break로 반복 자체를 끝내는 것이 핵심입니다.
• if i > start and nums[i] == nums[i - 1] — 위에서 설명한 같은 깊이 중복 제거입니다.
• backtrack(i + 1, remain - nums[i]) — 다음 시작을 i + 1로 넘겨 같은 원소를 다시 쓰지 않게 합니다. 같은 원소를 여러 번 써도 되는 문제라면 i를 넘깁니다.
• path.pop() — 되돌리기입니다. 이 줄이 없으면 다음 가지가 이전 선택에 오염됩니다.
• (row - col) in diag1 — 대각선 판별의 핵심입니다. 같은 대각선에 있으면 row - col이 같습니다. 반대 방향 대각선은 row + col이 같습니다. 이 성질 덕분에 O(1)로 충돌을 판단할 수 있습니다.
• nonlocal count — 중첩 함수에서 바깥 변수를 수정하겠다는 선언입니다. 없으면 새 지역 변수가 만들어져 값이 반영되지 않습니다.
• 행마다 하나씩만 놓으므로 행 충돌은 애초에 불가능합니다. 열과 두 대각선만 확인하면 됩니다. 이것도 탐색 공간을 줄이는 설계입니다.

N-퀸의 8×8 답은 92개입니다. 완전 탐색으로 64칸 중 8칸을 고르면 약 44억 가지지만, 행마다 하나 + 즉시 가지치기로 실제 탐색은 극히 일부만 이루어집니다.

⚠️ 자주 하는 실수

첫째, 되돌리기를 빠뜨립니다. path.pop()이나 set.remove()를 안 하면 이전 가지의 흔적이 남아 완전히 틀린 결과가 나옵니다. 선택과 되돌리기는 짝으로 씁니다.

둘째, 사본을 저장하지 않습니다. result.append(path)는 참조를 담습니다. 나중에 path가 비면 결과도 전부 빈 리스트가 됩니다. 반드시 path[:]나 list(path)로 복사하세요.

셋째, 가지치기가 정답을 자릅니다. 중복 제거 조건을 i > 0으로 쓰면 (2, 2) 같은 정당한 답까지 사라집니다. 가지치기를 넣은 뒤에는 작은 입력으로 답의 개수를 검증하세요.

넷째, 가지치기를 아예 안 합니다. 백트래킹 틀만 쓰고 조건을 안 넣으면 완전 탐색과 같습니다. "지금까지의 선택으로 이미 답이 불가능한가"를 매 단계에서 물으세요.

다섯째, 상태를 리스트로 관리해 O(n) 검사를 합니다. N-퀸에서 if col in placed_list처럼 리스트를 쓰면 O(n)입니다. 집합을 쓰면 평균 O(1)입니다(7강).

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	선택 → 탐색 → 되돌리기
2	결과는 반드시 사본으로 저장
3	가지치기가 성능을 결정한다
4	정렬 후 break는 뒤를 통째로 자른다
5	중복 제거는 같은 깊이에서만 (i > start)
6	가지치기가 정답을 자르지 않는지 검증
7	상태 검사는 집합으로 O(1)

지금 해 볼 것은 combination_sum에서 path[:]를 path로 바꿔 실행해 보는 것입니다. 결과가 빈 리스트들로 채워지는 것을 보면 사본 저장의 이유가 각인됩니다.

다음 17강 「그리디」에서는 전혀 다른 접근을 다룹니다. 모든 경우를 보지 않고 매 순간 가장 좋아 보이는 선택만 하는 방법입니다. 훨씬 빠르지만 항상 옳지는 않아서, 언제 쓸 수 있는지 판단하는 것이 관건입니다.

📚 참고 자료

• The nonlocal statement — Python 공식 문서
• Set Types — Python 공식 문서
• copy — Shallow and deep copy — Python 공식 문서