[Algorithm] 완전 탐색

1. 완전 탐색

모든 경우의 수를 탐색한다.

그래서 비용이 비싸다.

 

예를 들어

그래프의 인접 행렬에서 연결된 노드들을 반환할 때 완전 탐색을 하게 된다.

vector<vector<bool>> adjacent(6, vector<int>(6, 0));
adjacent[0][1] = true;
adjacent[1][1] = true;
adjacent[2][2] = true;

// 연결된 모든 노드 출력
for (int y = 0; y < 6; ++y)
{
    for (int x = 0; x < 6; ++x)
    {
        cout << x << " -> " << y << "\n";
    }
}

 

2. 백트래킹

백트래킹은 완전 탐색에서 가는 방향이 목표에 도달할 가능성이 없다고 판단되면

더 이상 그 경로를 탐색하지 않고 되돌아가는 것을 말한다.

모든 경우를 탐색하지 않고 조건에 따라 일정만 탐색하는 것을 말한다.

 

예시

Q.N과 N개의 자연수가 주어진다.
여기서 몇 개의 숫자를 골라 합을 mod11을 했을 때 나오는 가장 큰 수를 구하라

#include <iostream>
#include <vector>

using namespace std;

int n, temp, ret;
vector<int> v;
const int mod = 11;

// 완전 탐색
void go(int idx, int sum){
    // 백트래킹 조건
     if(idx == n){
         ret = max(ret, sum % mod);
         return;
     }
     go(idx + 1, sum + v[idx]);
     go(idx + 1, sum);
}

int main() {
     cin >> n;
     for(int i = 0; i < n; i++){
         cin >> temp;
         v.push_back(temp);
     }
     go(0, 0);
     cout << ret << "\n";
     return 0;
}

 

3. 원상복구

원상복구는 문제를 통해 살펴보자.

A에서 출발하여 특정 목적지(D)까지 갈 수 있는 모든 경로를 출력해야 한다.

그래프에서는 다음 노드에 도달하였을 때

순환 참조를 방지하기 위해 방문한 노드를 표시해 놓는다.

 

그러나 해당 문제에서는 목적지로 갈 수 있는 다양한 방법을 탐색해야함으로

한 번 방문한 노드를 풀지 않으면 모든 다양한 갈 수 있는 방법을 찾을 수 없게 된다.

 

예를 들어,

A,B,C,D / A D / A E F D 가 정답일 경우

A,B,C,D에 도달하는 순간 D는 방문한 것으로 체크되고

다음 경로인 A D / A E F D를 찾을 수 없게 된다.

 

즉 현재 상태를 유지하는 것이 아닌 돌아갔을 때 이전 상태를 유지하는 것을 원상복구라 한다.

 

예시

void go(int idx){
     if(v.size() == 3){
         print();
         return;
     }
    for(int there : adj[idx]){
        if(visited[there]) continue;
        // 다음 노드를 방문한 것으로 설정한다.
        visited[there] = 1;
        v.push_back(there);
        go(there);
        // 다시 돌아오면 노드를 방문하지 않은 것으로 설정한다.
        visited[there] = 0;
        v.pop_back();
    }
}