[알고리즘] 백트래킹(Backtracking) 이란?!

 

알고리즘 공부를 하다 보면 자주 등장하는 '백트레킹(Backtracking)'이란 알고리즘을 만나게 된다.

 

 

https://www.programiz.com/dsa/backtracking-algorithm

 

 

👀 백트레킹(Backtracking) 이란?

해를 찾는 도중 해가 아니어서 막히면 더이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 다시 해를 찾아내는 기법이라고 설명 할 수 있다.

현재 상태에서 가능한 모든 선택지를 하나씩 시도해보고, 조건에 맞지 않으면 이전 상태로 돌아가 다른 선택지를 탐색하는 방식으로 작동한다.

 

쉽게 말해, 문제를 해결하기 위해 하나의 길을 따라 탐색하다가 원하는 해답에 도달하지 못할 경우, 그 지점에서 "뒤로 돌아가(backtrack)" 다른 경로를 시도하는 방식이다.

 

백트레킹 알고리즘에서 가장 중요한 개념 중 하나가 "가지치기" 이다.

만족하지 못할 것으로 판단되는 경로를 더 이상 탐색하지 않고 빠르게 제거하여 불필요한 연산을 줄이는 방법이고, 효과적인 가지치기를 통해 탐색할 상태의 수를 현저히 줄일 수 있기 때문에 알고리즘의 성능 향상에 결정적이다.

 

👀 백트레킹은 주로 재귀 함수로 구현된다.

재귀 함수는 특정 상태에서 선택 가능한 모든 경로를 순차적으로 탐색하며, 선택된 경로가 문제의 조건을 만족하지 못하면 즉시 이전 상태로 돌아와 다른 선택지를 탐색하는 구조이다.

 

단계적으로 표현하면:

 

1. 현재 상태에서 가능한 선택

2. 선택한 상태가 조건 만족?: ✅ / ❌

3. 조건 만족 시 더 깊게 탐색 (재귀)

4. 조건을 만족하지 않으면 현재 상태를 포기하고 이전 상태로 돌아가(backtrack) 다음 선택지를 탐색

 

 

 

위 개념을 코드로 적용해본다.

 

백준 https://www.acmicpc.net/problem/15650 문제를 가지고 왔다.

 

 

 

N, M = map(int, input().split())

def backtracking(N, M, start , seq):
    if len(seq) == M: # 목표한 길이가 되었으면 return
        print(seq)
        return
    
    for i in range(start, N+1):
        seq.append(i)
        backtracking(N, M, i+1, seq)
        seq.pop()


backtracking(N, M, 1, [])

 

재귀 함수를 통하여 목표된 길이를 설정하고 return을 해준다.

 

좀 더 도식화 하여 보여드리자면

 

backtracking(4, 2, 1, [])
│
├─ i=1 → seq.append(1) ➡ seq=[1]
│   ├─ backtracking(4, 2, 2, [1])
│   │   ├─ i=2 → seq.append(2) ➡ seq=[1,2] ✅ 출력: [1,2]
│   │   │        → seq.pop() ➡ seq=[1] 🔙 복구
│   │   ├─ i=3 → seq.append(3) ➡ seq=[1,3] ✅ 출력: [1,3]
│   │   │        → seq.pop() ➡ seq=[1] 🔙 복구
│   │   └─ i=4 → seq.append(4) ➡ seq=[1,4] ✅ 출력: [1,4]
│   │            → seq.pop() ➡ seq=[1] 🔙 복구
│   │
│   └─ seq.pop() ➡ seq=[] 🔙 복구
│
├─ i=2 → seq.append(2) ➡ seq=[2]
│   ├─ backtracking(4, 2, 3, [2])
│   │   ├─ i=3 → seq.append(3) ➡ seq=[2,3] ✅ 출력: [2,3]
│   │   │        → seq.pop() ➡ seq=[2] 🔙 복구
│   │   └─ i=4 → seq.append(4) ➡ seq=[2,4] ✅ 출력: [2,4]
│   │            → seq.pop() ➡ seq=[2] 🔙 복구
│   │
│   └─ seq.pop() ➡ seq=[] 🔙 복구
│
├─ i=3 → seq.append(3) ➡ seq=[3]
│   ├─ backtracking(4, 2, 4, [3])
│   │   └─ i=4 → seq.append(4) ➡ seq=[3,4] ✅ 출력: [3,4]
│   │            → seq.pop() ➡ seq=[3] 🔙 복구
│   │
│   └─ seq.pop() ➡ seq=[] 🔙 복구
│
└─ i=4 → seq.append(4) ➡ seq=[4]
    └─ backtracking(4, 2, 5, [4]) ❌ 길이 부족 (종료)
         → seq.pop() ➡ seq=[] 🔙 복구

 

 

seq.append()를 통해 선택을 수행하고, 조건을 만족하지 못하거나 조건을 만족한 뒤에도, 이전 상태로 정확히 되돌리기 위해서 seq.pop()이 반드시 호출된다.

 

위 도식화를 통해 백트레킹 알고리즘이 상태 공간 트리에서 어떻게 깊이 우선 탐색(DFS)을 수행하는지, 재귀적으로 탐색하고 복구하는 과정이 어떻게 이루어지는지 더 명확히 이해할 수 있을 것이다.