1. 백트래킹이란?
백트래킹(Backtracking)은 재귀(Recursion)를 이용하여 모든 가능한 경우의 수를 탐색하는 알고리즘 중 하나입니다. 각 단계에서 가능한 모든 선택지를 시도해보고, 만약 잘못된 선택을 했다면 그 선택 이전 상태로 돌아가서 다른 선택지를 시도합니다. 이를 "되돌아가기" 또는 "백트래킹"이라고 부릅니다.
백트래킹은 문제 해결 과정에서 조건을 만족하지 않는 경로는 더 이상 탐색하지 않고 가지치기(pruning) 하는 것이 핵심입니다. 이를 통해 불필요한 탐색을 줄여서 효율적으로 해결할 수 있습니다.
특징
- 재귀적으로 문제를 해결한다.
- 완전탐색의 일종이지만, 가지치기를 통해 성능을 향상시킨다.
- 모든 가능한 경우를 살펴보면서도, 잘못된 경로는 빨리 포기한다.
2. 백트래킹의 동작 과정
백트래킹을 단계별로 나누어 설명하면 이해하기가 쉽습니다.
2.1 기본 구조
백트래킹 알고리즘은 크게 세 단계로 나눌 수 있습니다.
- 문제 해결을 위한 선택지 제시
문제의 각 단계에서 선택할 수 있는 여러 옵션이 있다면, 이 옵션을 하나씩 시도합니다. - 해가 유효한지 확인
현재 선택한 해가 조건을 만족하는지 확인합니다. 조건을 만족하지 않으면 더 이상 진행하지 않고 돌아갑니다. - 종료 조건
만약 유효한 해이고 문제를 완전히 해결했다면, 해당 해를 저장하거나 출력합니다.
백트래킹 알고리즘에서 1번은 재귀 호출을 통해 구현되며, 2번과 3번은 재귀 호출 안에서 처리됩니다.
각 단계가 코드에 어떻게 구현되는지 살펴볼게요:
1. 문제 해결을 위한 선택지 제시 (재귀 호출)
이 부분은 백트래킹의 핵심입니다. 문제의 각 단계에서 여러 가지 선택을 할 수 있을 때, 그 선택들을 하나씩 시도하는 과정입니다. 이때 선택할 수 있는 모든 경우를 재귀적으로 탐색합니다.
- 예를 들어, N과 M 문제에서
dfs(depth)함수는 현재 깊이에서 가능한 숫자를 선택한 후, 그 숫자에 대해 다시 다음 깊이로 이동하는 방식으로 동작합니다.
2. 해가 유효한지 확인 (가지치기)
이 부분은 각 선택이 유효한지 판단하는 역할을 합니다. 유효하지 않으면 더 이상 진행하지 않고 선택을 취소하고, 유효하면 계속 진행합니다.
- 예를 들어, 이미 방문한 숫자를 다시 선택하지 않도록
visit[]배열을 사용하여 방문 여부를 확인하는 것이 이 과정입니다.
3. 종료 조건 (기저 조건)
이 부분은 재귀 호출이 더 이상 진행되지 않고 종료되도록 하는 조건입니다. 주로 재귀 호출의 깊이가 일정 값에 도달했을 때, 즉 문제에서 요구하는 해의 조건을 만족했을 때 종료됩니다. 문제를 완전히 해결했으면 결과를 출력하거나 저장합니다.
- 예를 들어, N과 M 문제에서는
depth == m이 될 때 모든 숫자를 선택한 것이므로 출력하는 부분이 여기 해당합니다.
코드에서의 구현
public class Main {
static int[] arr; // 선택된 숫자들을 저장할 배열
static boolean[] visit; // 숫자의 방문 여부를 저장할 배열
static int n, m;
// 1. 백트래킹 함수 (문제 해결을 위한 선택지 제시)
public static void dfs(int depth) {
// 3. 종료 조건: M개의 숫자를 모두 선택했을 때 결과를 출력하고 종료
if (depth == m) {
for (int i = 0; i < m; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
// 1. 가능한 선택지(1부터 N까지의 숫자)를 시도
for (int i = 1; i <= n; i++) {
// 2. 해가 유효한지 확인 (이미 선택된 숫자는 다시 선택하지 않음)
if (!visit[i]) {
visit[i] = true; // i를 선택
arr[depth] = i; // 현재 깊이에 선택한 숫자를 저장
dfs(depth + 1); // 재귀 호출로 다음 깊이로 이동 (선택지 제시)
visit[i] = false; // 백트래킹: 선택을 취소하고 다시 다른 선택 시도
}
}
}
public static void main(String[] args) {
// 입력 받기 및 초기화
n = 3; // N 값
m = 2; // M 값
arr = new int[m];
visit = new boolean[n + 1]; // 1부터 n까지 사용하므로 크기 n+1
dfs(0); // 깊이 0부터 시작 (최초 재귀 호출)
}
}요약하자면:
- 1번 (재귀 호출):
dfs(depth + 1)로 다음 깊이로 넘어가는 것이 재귀 호출입니다. 모든 가능한 선택지를 탐색합니다. - 2번 (유효성 확인):
if (!visit[i])조건으로 선택한 숫자가 유효한지(이미 방문한 숫자인지) 확인하고, 유효하지 않으면 가지치기를 합니다. - 3번 (종료 조건):
if (depth == m)에서, 해가 완성되었을 때 결과를 출력하고 종료합니다.
이처럼 1번이 재귀 호출을 통한 선택의 확장이고, 2번과 3번이 재귀 호출 안에서 각각 유효성 검사와 종료 조건으로 구현됩니다.
2.2 기본 흐름
- 재귀 호출
가능한 모든 선택지를 탐색하며, 다음 단계로 이동하기 위해 재귀적으로 함수가 호출됩니다. - 가지치기
조건을 만족하지 않으면 해당 경로를 포기하고 다른 경로로 돌아가며 새로운 선택을 시도합니다. - 종료
모든 경우의 수를 탐색하면 종료됩니다.
3. 백트래킹의 예시
백트래킹 알고리즘을 이해하는 가장 좋은 방법은 실제 문제에 적용해 보는 것입니다. 다음은 백트래킹을 적용할 수 있는 대표적인 문제들입니다.
3.1 N과 M (백준 15649번 문제)
1부터 N까지의 자연수 중에서 중복 없이 M개의 수를 고르는 모든 경우를 출력하는 문제입니다.
문제 예시:
입력: N = 3, M = 2
출력:
1 2
1 3
2 1
2 3
3 1
3 2코드 구조:
public class Main {
static int[] arr; // 선택된 숫자들을 저장할 배열
static boolean[] visit; // 숫자의 방문 여부를 저장할 배열
static int n, m;
// 백트래킹 함수
public static void dfs(int depth) {
if (depth == m) { // M개의 숫자를 모두 선택했을 때 출력
for (int i = 0; i < m; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
for (int i = 1; i <= n; i++) {
if (!visit[i]) { // 선택되지 않은 숫자를 찾음
visit[i] = true; // 방문 처리
arr[depth] = i; // 선택된 숫자를 배열에 저장
dfs(depth + 1); // 재귀 호출을 통해 다음 숫자를 선택
visit[i] = false; // 백트래킹: 방문 처리 해제
}
}
}
public static void main(String[] args) {
// N과 M을 입력받고 초기화
n = 3;
m = 2;
arr = new int[m];
visit = new boolean[n + 1];
dfs(0); // 깊이 0부터 백트래킹 시작
}
}4. 백트래킹의 장단점
4.1 장점
- 완전탐색을 통해 모든 가능한 해를 찾을 수 있습니다.
- 가지치기를 통해 불필요한 경로를 탐색하지 않으므로 효율적입니다.
- 다양한 문제에 쉽게 적용할 수 있으며, 문제를 간단하게 모델링할 수 있습니다.
4.2 단점
- 최악의 경우에는 여전히 지수 시간 복잡도를 가질 수 있습니다.
- 모든 경로를 탐색해야 하는 문제에서는 시간이 오래 걸릴 수 있습니다.
- 메모리 사용량이 많을 수 있습니다(재귀 호출이 깊어질수록 스택 메모리를 많이 사용).
5. 백트래킹을 사용하는 문제 유형
백트래킹 알고리즘은 다음과 같은 문제들에서 자주 사용됩니다.
5.1 순열(Permutations) 및 조합(Combinations)
- 순열 문제: N개의 원소 중에서 M개를 뽑아 나열하는 문제.
- 조합 문제: N개의 원소 중에서 M개를 뽑되, 순서를 고려하지 않는 문제.
5.2 그래프 탐색 문제
- 미로 찾기: 시작점에서 목표점까지의 경로를 찾되, 잘못된 경로는 되돌아가는 방식으로 해결합니다.
- N-Queen 문제: N개의 퀸이 서로 공격하지 않도록 체스판에 놓는 방법을 찾는 문제입니다.
5.3 퍼즐 문제
- Sudoku: 9x9 퍼즐을 규칙에 맞게 채우는 문제.
- Knapsack 문제: 물건을 배낭에 담을 때 최적의 해를 구하는 문제.
6. 백트래킹과 다른 알고리즘의 비교
6.1 완전탐색(Brute Force) vs 백트래킹
- 완전탐색: 가능한 모든 경우를 무조건 탐색.
- 백트래킹: 조건을 만족하지 않는 경우는 가지치기를 통해 탐색하지 않고 돌아감.
6.2 동적 계획법(Dynamic Programming) vs 백트래킹
- 동적 계획법: 문제를 작은 하위 문제로 분할하고, 그 결과를 저장하여 재활용하는 방식으로 효율적으로 문제를 해결.
- 백트래킹: 문제를 해결하는 과정에서 가능한 모든 경로를 탐색하지만, 불필요한 경로는 빠르게 포기.
7. 백트래킹을 적용할 때 주의할 점
- 기저 조건 설정: 재귀 호출에서 반드시 종료 조건을 명확히 설정해야 무한 루프에 빠지지 않습니다.
- 메모리 관리: 재귀 호출의 깊이가 깊어질수록 메모리를 많이 사용하므로, 재귀 호출 횟수에 주의해야 합니다.
- 가지치기(pruning): 불필요한 탐색을 막기 위해 조건을 적절히 설정하고 가지를 치는 것이 중요합니다.
8. 요약
백트래킹은 여러 선택지가 주어진 문제에서 조건을 만족하는 해를 찾기 위한 강력한 알고리즘입니다. 모든 경우를 탐색할 때 적합하며, 가지치기를 통해 불필요한 경로를 탐색하지 않아 효율적으로 문제를 해결할 수 있습니다.
