[이론] 완전 탐색과 백트래킹

 

완전 탐색과 백트래킹은 코딩 테스트에서 중요한 탐색 기법으로, 문제에서 가능한 모든 경우의 수를 고려하여 최적의 해답을 찾는 데 사용된다. 오늘은 완전 탐색과 백트래킹이 어떤 개념인지 알아보도록 하겠다.

 

---

완전 탐색 (Brute Force)

 

 

완전 탐색(Brute Force)은 모든 가능한 경우를 무식하게 하나하나 다 확인하는 방식으로 문제를 해결한다.

 

가능한 모든 조합, 모든 배열 등을 전부 시도해본 뒤 조건에 맞는 결과를 찾는다.

따라서 완전 탐색은 가장 단순한 방법이지만, 시간 복잡도가 클 수 있으니 입력의 크기를 잘 확인해야 한다.

 

간단한 문제로 확인해보겠다.

 

 

 

백준 2309번: 일곱 난쟁이

https://www.acmicpc.net/problem/2309

 

✅ 코드 확인

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int people[9], isVisited[9];
vector<int> answer;

void dfs_combi(int sum, int r, int cur, int depth) {
    if (depth == r && sum == 100) {
        for (int i = 0; i < 9; i++)
            if (isVisited[i])
                answer.push_back(people[i]);
        sort(answer.begin(), answer.end());
        for (int i : answer)
            cout << i << '\n';
        exit(0);
    }
    
    for (int i = cur; i < 9; i++) {
        if (isVisited[i]) continue;
        isVisited[i] = 1;
        dfs_combi(sum + people[i], r, i, depth + 1);
        isVisited[i] = 0;
    }
}

int main()
{
    for (int i = 0; i < 9; i++)
        cin >> people[i];
    dfs_combi(0, 7, 0, 0);
    return 0;
}

 

📚 문제 접근

 

이 문제는 9명의 난쟁이 중 7명을 뽑아 몸무게의 합이 100이 되는 경우를 찾는 문제이다.

즉, 9C7 조합(Combination) 문제를 코드로 나타낼 수 있는가에 대한 문제로 볼 수 있다.

만약 이해가 안된다면 이전에 포스팅한 '순열과 조합'을 참고하길 바란다.

 

https://gus6615.tistory.com/89

 

 

물론 조합이 아닌, 순열(Permutation)으로도 해결할 수도 있다.

아래 더보기는 순열을 활용한 풀이 방식이다.

#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE 9

using namespace std;

int main() {
	ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

	vector<int> heights(SIZE, 0);

	for (int i = 0; i < SIZE; i++) {
		int tmp;
		cin >> tmp;
		heights[i] = tmp;
	}

	sort(heights.begin(), heights.end());
	vector<int> checks = { 1, 1, 1, 1, 1, 1, 1, 0, 0 };

	do {
		int sum = 0;
		for (int i = 0; i < SIZE; i++)
			if (checks[i])
				sum += heights[i];

		if (sum == 100)
			break;
	} while (prev_permutation(checks.begin(), checks.end()));

	for (int i = 0; i < SIZE; i++)
		if (checks[i])
			cout << heights[i] << "\n";

	return 0;
}

이처럼 모든 경우에 대해 특정 조건을 만족할 때까지 탐색하는 과정을 완전 탐색(Bruth Force)라고 부른다.

 

 

 

---

백트래킹(Backtracking)

 

 

백트래킹(Backtracking)은 완전 탐색의 단점을 보완하기 위해, 탐생 도중 불필요한 경로를 가지치기(Pruning)하여 탐색을 줄이는 방식이다.

 

위 사진은 '일곱 난쟁이' 문제를 백트래킹의 관점으로 본 사진이다.

특정 구간에서 sum이 100을 넘기면 그 아래 구간은 탐색하지 않도록 한다.

이처럼 문제 조건을 만족하지 않는 경로가 발견되면 그 경로를 더 이상 탐색하지 않고 돌아가며 탐색 범위를 줄인다.

 

일곱 난쟁이 문제레 백트래킹 개념을 추가하면 다음과 같다.

 

 

 

백준 2309번: 일곱 난쟁이

https://www.acmicpc.net/problem/2309

 

✅ 코드 확인

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int people[9], isVisited[9];
vector<int> answer;

void dfs_combi(int sum, int r, int cur, int depth) {
    // 백트래킹 추가
    if (sum > 100) return;
    
    if (depth == r && sum == 100) {
        for (int i = 0; i < 9; i++)
            if (isVisited[i])
                answer.push_back(people[i]);
        sort(answer.begin(), answer.end());
        for (int i : answer)
            cout << i << '\n';
        exit(0);
    }
    
    for (int i = cur; i < 9; i++) {
        if (isVisited[i]) continue;
        isVisited[i] = 1;
        dfs_combi(sum + people[i], r, i, depth + 1);
        isVisited[i] = 0;
    }
}

int main()
{
    for (int i = 0; i < 9; i++)
        cin >> people[i];
    dfs_combi(0, 7, 0, 0);
    return 0;
}

 

위 코드는 기저 사례에서 문제의 조건을 만족하지 않는지 체크하여 불필요한 탐색을 줄인다.

이를 통해 완전 탐색의 단점을 해결할 수 있다.

 

 

 

---

정리

완전 탐색 vs 백트래킹

 

방법	특징	시간 복잡도	예시
완전 탐색	가능한 모든 경우를 다 탐색	O(n!), O(2^n), O(n^k)	조합, 순열 문제 등
백트래킹	조건에 따라 불필요한 경우의 수를 가지치기하여 탐색	보통 완전 탐색보다 적음	N-Queens, 미로 탐색 문제 등

 

 

완전 탐색은 문제의 모든 경우를 탐색할 때, 백트래킹은 조건을 통해 탐색 경로를 줄일 때 유리하다.

특히 조합이나 순열을 구할 때 백트래킹을 활용하면, 불필요한 경로를 제거하여 더 효율적으로 답을 찾을 수 있다.