🤔 백트래킹(Backtracking) 이란?
일단 가보고, 아니면 돌아와!
백트래킹(Backtracking)이란, 해를 찾는 도중에 잘못된 해를 만나면 다시 되돌아가서 해를 탐색하는 기법을 말한다.
백트래킹 기법은 모든 경우의 수를 탐색하는 브루트포스(Brute-Force)와 비슷해 보이지만, 훨씬 효율적이다. 백트래킹은 가지치기(Pruning)를 사용하기 때문이다. 가지치기(Pruning)란, 정답이 될 가능성이 없는 경로는 더 이상 탐색하지 않고 과감히 잘라내는 작업을 의미한다. 이 과정을 통해 불필요한 탐색을 줄일 수 있다.
주로 깊이 우선 탐색(DFS, Depth First Search)로 수행한다. DFS를 구현하는 방식은 재귀 함수와 스택으로 나누어진다. 이번 백트래킹 알고리즘은 재귀함수를 이용하여 구현할 것이다.
📌 재귀 함수 vs 스택
재귀 함수를 사용하는 이유는 무엇일까? "마법 같은 상태 복원"을 이유로 들 수 있겠다. 재귀 함수를 이용하면 함수가 호출될 때마다 현재 상태(경로, 변수 값 등)가 함수 호출 스택에 자동으로 저장된다. 그리고 수행을 마치고 함수가 return 되면, 자연스럽게 이전의 상태로 돌아갈 수 있다. 함수 return만으로도 되돌아가는 과정이 구현되는 것이다.
그러나 스택을 사용하면 변경 사항을 모두 이전 상태로 되돌리는 작업을 직접 수행해야한다. 잘못된 해를 만났을 때 이전 상태를 저장해두었다가 다시 찾아서 되돌리는 과정을 일일이 구현해야 하는 것이다. 백트래킹 알고리즘을 진행과 후퇴가 반복되는 알고리즘인데 스택을 이용하면 구현 과정이 무척 번거롭고 복잡해질 것이다. 따라서 백트래킹을 구현할 때는 재귀함수를 이용하는 것이 유리하다.
📖 백트래킹으로 해결할 수 있는 문제는?
백트래킹은 주로 모든 해를 찾을 때, 특정 조건을 만족하는 해를 찾을 때, 최적의 해를 찾을 때 사용된다. 이는 크게 최적화(optimization) 문제와 결정(decision) 문제로 나누어 볼 수 있다.
- 최적화 문제: 최솟값이나 최댓값을 구하는 문제. ex) 여행자 문제(Traveling Salesman Problem, TSP) 등.
- 결정 문제: 문제의 조건을 만족하는 해가 존재하는지의 여부를 답하는 문제. ex) 미로 찾기, N-Queen, 부분합(Subset Sum) 문제 등.
✍🏻 관련 문제
❓ 문제
백준 15649번: N과 M (1) https://www.acmicpc.net/problem/15649
백준 15650번: N과 M (2) https://www.acmicpc.net/problem/15650
백준 15651번: N과 M (3) https://www.acmicpc.net/problem/15651
백준 15652번: N과 M (4) https://www.acmicpc.net/problem/15652
백준 15654번: N과 M (5) https://www.acmicpc.net/problem/15654
백준 15655번: N과 M (6) https://www.acmicpc.net/problem/15655
백준 15656번: N과 M (7) https://www.acmicpc.net/problem/15656
백준 15657번: N과 M (8) https://www.acmicpc.net/problem/15657
백준 15663번: N과 M (9) https://www.acmicpc.net/problem/15663
백준 15664번: N과 M (10) https://www.acmicpc.net/problem/15664
💡문제풀이
'이론' 카테고리의 다른 글
| [이론_Java 기초] Queue 구현체 비교 (0) | 2026.02.02 |
|---|---|
| [이론] 다익스트라 알고리즘 (0) | 2025.12.14 |
| [이론] 최장 공통 부분 수열 (LCS, Longest Common Subsequence) (0) | 2025.10.01 |
| [이론] 배낭 문제 (0) | 2025.10.01 |
| [이론] 유클리드 호제법 (0) | 2025.09.10 |