백트래킹(Backtracking)의 이해

백트래킹(Backtracking)은 알고리즘 문제를 풀 때 "모든 경우의 수를 다 찾아보되, 정답이 될 가능성이 없는 길은 중간에 포기하고 되돌아가는 방식"입니다.

DFS(깊이 우선 탐색)와 아주 밀접한 관계가 있는데요.

1. 백트래킹의 핵심: "가지치기(Pruning)"

DFS는 기본적으로 "모든 곳을 다 찔러보는" 무식한(완전 탐색) 방법입니다. 하지만 어떤 문제에서는 굳이 끝까지 안 가봐도 "아, 이 길은 어차피 정답이 아니네" 하고 중간에 알 수 있는 경우가 있습니다.

일반 DFS: "일단 끝까지 다 파보자! (모든 경우의 수 탐색)"
백트래킹: "끝까지 파보다가 뭔가 조건에 안 맞으면 더 이상 안 파고, 바로 이전 단계로 돌아가서(Backtrack) 다른 길을 찾자!"

이렇게 쓸데없는 경로를 일찍 차단하는 것을 나무의 가지를 자른다는 의미로 가지치기(Pruning)라고 부르며, 이것이 백트래킹의 핵심입니다.

2. 작동 방식 (상태 되돌리기)

백트래킹은 재귀함수를 통해 구현하며, 반드시 지켜야 하는 패턴이 있습니다.

현재 상태를 배열 등에 추가하고 "방문(사용)했다"고 표시합니다.
재귀함수를 호출해서 다음 단계로 깊게 들어갑니다.
재귀함수에서 빠져나왔을 때, 방금 추가했던 상태를 다시 빼고 "방문 안 했다"로 되돌려놓습니다 (원상복구).

이 "원상복구" 과정이 있어야 이전 분기점으로 돌아와서 다른 숫자를 선택해 볼 수 있습니다.

3. 대표 예제: N과 M

1부터 N까지의 자연수 중 중복 없이 M개를 고르는 수열(순열)을 모두 출력하는 문제로, 백트래킹의 가장 완벽한 튜토리얼입니다.

python# 예: 1부터 3까지의 숫자 중 2개를 고르는 모든 경우의 수 (N=3, M=2)
N = 3 
M = 2 

# 현재까지 고른 숫자를 담을 리스트
ans = []  

def backtrack():
  # 1. 종료 조건: M개의 숫자를 모두 골랐다면 출력 후 종료   
    if len(ans) == M:
        print(" ".join(map(str, ans)))
        return
   # 2. 가능한 모든 선택지를 반복
    for i in range(1, N + 1): 
        # 3. 가지치기: 이미 고른 숫자는 건너뛴다 (조건 확인)    
        if i not in ans:
            # (1) 상태 변경 (숫자 선택)  
            ans.append(i)

            # (2) 다음 단계로 이동 (재귀 호출)    
            backtrack()

            # (3) 원상복구 (상태 되돌리기) ⭐️ 백트래킹의 핵심         
            ans.pop()  

backtrack()

Output