BackTracking(백트래킹)

✅ BackTracking(백트래킹)

백트래킹(Backtracking) 알고리즘은 해를 찾는 도중 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법입니다. 즉, 가능성이 없는 경로는 미리 배제하여 탐색을 최적화하는 DFS(깊이 우선 탐색)의 변형이라고 할 수 있습니다.

백트래킹 알고리즘은 다음과 같은 문제를 해결하는 데 사용됩니다:

• 최적화(Optimization) 문제: 최적의 해를 찾는 문제
• 결정(Decision) 문제: 특정 조건을 만족하는 해가 존재하는지 확인하는 문제

재귀함수를 이용한 백트래킹 시각화

 

✅ 백트래킹 vs 깊이 우선 탐색(DFS) 차이점

개념깊이 우선 탐색 (DFS)백트래킹 (Backtracking)

개념	깊이 우선 탐색(DFS)	백트래킹(BackTracking)
기본 개념	모든 가능한 경로를 탐색	불가능한 경로를 조기에 차단
Pruning 가지치기	없음 (모든 경로 탐색)	있음 (해결책이 아닐 경우 중단)
시간 복잡도	최악의 경우 모든 경우 탐색 (지수적 증가 가능)	불필요한 탐색을 줄여 일반적으로 DFS보다 빠름
사용 예시	그래프 탐색, 경로 찾기	N-Queen 문제, 부분집합, 순열, 조합 문제
처리 가능 크기	경우의 수가 많으면 비효율적 (예: N!N!N! 경우의 수)	경우의 수를 줄일 수 있지만 여전히 최악의 경우 지수 시간

 

 DFS는 무조건 모든 경로를 탐색하지만, 백트래킹은 "가능성이 없는 경로"를 미리 차단하여 탐색 속도를 향상시킨다. 하지만 백트래킹도 최악의 경우 여전히 지수 시간이 걸릴 수 있다.

 

 

1️⃣ 백트래킹 개념 쉽게 이해하기

✅ 예제 1: 미로에서 길 찾기

 

미로에서 길을 찾는 방법을 생각해보면:

1. 길을 따라가다가 막힌 길이면 되돌아감 🛑
2. 길이 열려 있으면 계속 전진 ✅
3. 목표에 도달하면 탐색 종료 🎯

✔ DFS vs 백트래킹 차이점

• DFS는 "모든 경로를 다 탐색"하지만,
• 백트래킹은 "가능성이 없는 경로는 미리 포기"하여 탐색 속도를 향상시킴.

---

2️⃣ 백트래킹 예제 코드 (재귀 활용)

✔ 문제: 1부터 N까지 숫자로 이루어진 모든 순열을 생성하는 알고리즘

def backtrack(path, used, n):
    if len(path) == n:  # 모든 숫자가 선택되었으면 출력
        print(path)
        return
    
    for num in range(1, n + 1):
        if num not in used:  # 이미 선택된 숫자는 사용하지 않음
            path.append(num)  # 선택
            used.add(num)  # 방문 체크
            backtrack(path, used, n)  # 재귀 호출
            path.pop()  # 원상 복구 (백트래킹)
            used.remove(num)

n = 3
backtrack([], set(), n)

 

✅ 실행 결과 (N=3)

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

 

📌 설명:

• 숫자를 하나씩 선택하며 가능한 경우만 탐색
• DFS와 다른 점: 이미 선택한 숫자는 다시 사용하지 않음 (가지치기 Pruning)

---

3️⃣ 백트래킹의 활용 예시

문제 유형예제

문제 유형	예제
경로 탐색	미로 찾기, 그래프 탐색
조합 문제	부분집합, 조합 생성
순열 문제	N-Queen 문제, 숫자 순열
최적화 문제	배낭 문제, 수식 계산

 

✅ 실제 활용 예제

• N-Queen 문제: 체스판 위에서 N개의 퀸이 서로 공격하지 않도록 배치하는 문제
• 비밀번호 크래킹: 가능한 조합을 하나씩 시도하며 탐색

 

📝 한 문장으로 정리하면?

 

 "백트래킹은 해가 될 가능성이 있는 경우만 탐색하고, 아닐 경우 조기에 포기하는 최적화된 DFS 기법이다!" 

 미로 찾기, 순열 생성, 조합 문제 등에 활용할 수 있으며, 가지치기를 통해 속도를 높인다!