[자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

 

DFS

2024.12.19 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그래프 + DFS

[자료구조 & 알고리즘] 그래프 + DFS

 

백트래킹 (Backtracking)

백트래킹은 DFS(Depth-First Search)를 기반으로 한 알고리즘 기법으로, 해를 찾기 위해 가능한 모든 경우를 탐색하지만, 불필요한 탐색을 줄이는 방법을 제공합니다. 주로 재귀를 이용해 구현되며, 문제를 해결할 때 정답이 될 가능성이 없는 경로를 조기에 차단하여 성능을 향상시킵니다.

 

백트래킹: 현재 상태에서 가능한 모든 후보군을 따라들어가며 탐색하는 알고리즘

 

백트래킹의 알고리즘 동작 원리는 [바킹독의 실전 알고리즘] 0x0C강 - 백트래킹 을 보고 학습하였으며, 

상태공간트리를 만드는 과정이라고 이해함으로서 백트래킹의 과정에 대하여 학습하였습니다.

상태공간트리란 위에서 언급한 "현재 상태에서 가능한 모든 후보군을 트리로 나타낸 것" 이라고 이해할 수 있습니다.

 

백트래킹에서 DFS가 어떻게 작용하는지 이해하는데는 N과 M계열의 문제가 효과적이었고, 상태공간트리의 개념을 이해하는데는 N-Queen 문제가 직관적이었습니다.

 

https://blog.encrypted.gg/945

 

N-Queen 문제를 간단히 요약하자면 N*N 배열안에 N개의 Queen을 배치할 수 있는 경우의 수를 카운팅하는 것입니다.

우측의 트리가 "상태공간트리"인데, 직관적으로 보면 각 층(lavel)은 행을 나타내고 있습니다. A1에 퀸을 놓았을 때 두번째 행인 B행에 퀸을 놓을 수 있는 경우의 수 (B3, B4)를 따져보고 세번째 행인 C행에 퀸을 놓을 수 있는 경우의 수를 따지면서 N행(리프노드)까지 도달하는 것이 목표입니다. N행에 도달하는 것이 목표인 이유는 각 행에 퀸을 하나씩 밖에 놓을 수 없기 때문입니다. 즉 N이 4로 주어졌을 경우 A,B,C,D 행에 퀸을 전부 놓을 수 있는 것, 즉 깊이가 리프노드까지 도달할 수 있는 것이 정답이 됩니다.

 

DFS가 백트래킹 문제를 위한 기본 도구라고 생각하고 상태공간트리의 전반적인 움직임을 파악한 후, 탐색 종료 지점까지 프로세스가 설계되었으면, 탐색 기법으로 DFS를 활용하여 코드를 구현하면 백트래킹의 알고리즘의 기초 설계가 가능한 것 같습니다.

---

1. 특징

1. 분기 한정 (Branch and Bound)
   모든 경우를 살펴보지 않고, 유망하지 않은 경로를 탐색에서 제외합니다.
   예: 순열 생성 시 이미 선택된 숫자는 제외.
2. DFS와의 차이점
   DFS는 단순히 모든 경로를 탐색하지만, 백트래킹은 특정 조건을 만족하지 않으면 재귀 호출을 중단하고 이전 단계로 돌아갑니다.
3. 효율성
   완전탐색과 비교하면 훨씬 적은 경로를 탐색하므로, 계산량을 줄일 수 있습니다.

---

2. 활용 분야

1. 순열과 조합 생성
   가능한 모든 순열과 조합을 찾되, 불필요한 경로를 제외.
2. 미로 탐색
   출구를 찾는 과정에서 유망하지 않은 경로를 막음.
3. Subset Sum 문제
   주어진 집합에서 특정 합을 만족하는 부분 집합 찾기.
4. N과 M (1) 문제
   1부터 N까지 자연수 중에서 M개의 수를 고르는 순열 생성.

---

3. C 코드 예제: N과 M (1)

#include <stdio.h>

#define MAX 8

int N, M;
int sequence[MAX];
int visited[MAX + 1];

void backtrack(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", sequence[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            sequence[depth] = i;
            backtrack(depth + 1);
            visited[i] = 0;
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    backtrack(0);
    return 0;
}

---

4. 작동 원리

시작
├── 1
│   ├── 2 → [1, 2]
│   └── 3 → [1, 3]
├── 2
│   ├── 1 → [2, 1]
│   └── 3 → [2, 3]
└── 3
    ├── 1 → [3, 1]
    └── 2 → [3, 2]

 

1. 숫자를 순차적으로 선택하면서 조건에 맞는 경우만 재귀 호출.
2. 선택된 숫자는 visited 배열을 통해 중복 방지.
3. M개의 숫자를 모두 선택하면 결과를 출력.
4. 모든 경우를 탐색한 후, 선택 상태를 초기화하고 이전 단계로 복귀.

---

5. 장단점

• 장점: 불필요한 탐색을 줄여 효율적.
• 단점: 조건이 많아질수록 가지치기 로직이 복잡해질 수 있음.