1. 완전탐색

모든 경우의 수를 탐색하는 알고리즘으로, 순열 or 조합 or 기타 다양한 경우의 수 의 탐색 방법을 반복문 or DFS or BFS 로 완전 탐색하는 유형이다.

완전 탐색은 방향성이있다. 즉, 한 방향으로 쭉 진행하며 밀어붙여야한다.

(1) 사용하는 경우

전체 경우의 수를 다 검사해봐도 연산량 고려했을때 시간 제한을 통과하는 경우

(2) 의사결정트리

문제 해결을 위한 모든 선택지를 트리 형태로 표현한 것

문제를 완전 탐색으로 접근할때 -> 문제를 의사결정트리로 만드는게 매우 매우 매우 중요하다.

(3) 구현 방법

✍ 반복문

for문 또는 반복문을 이용해 주어진 범위를 모두 검사하는 방법

• 반복문으로 완전 탐색 구현이 가능하면, 재귀말고 반복문을 쓰는것이 좋다 (반복문으로 구현하는 방식의 코스트가 더 적다)

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;

    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}

✍ DFS

DFS를 이용해 주어진 범위를 모두 검사히는 방법

• 반복문보다 코스트가 크다 (시간이 오래 걸린다)
• DFS로 구현하는 경우
  • 반복문으로 구현하기 힘든 경우
  • 매개변수가 수정되며 반복되는 경우
  • nC1, nC2, nC3 .. 등 이런 경우의 수를 다 생각해야 하는 경우

✍ next_permutation

순열을 이용해 주어진 범위를 모두 검사하는 방법

int solution(string numbers) {
    sort(numbers.begin(), numbers.end());
    do {
        for(int i=0;i<numbers.size();i++) {
            st.insert(atoi(numbers.substr(0, i+1).c_str()));     
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    for(int a : st) {
        if(is_prime(a)) ret++;
    }
    return ret;
    
}

위와같이 하면 주어진 문자열의 모든 부분 순열(=순열의 부분)을 탐색할 수 있다.

✍ A. 의사 결정 트리가 바로 안그려지는 경우 -> 앞에서부터 DFS로 완전 탐색

가능한 모든 합을 찾는 예시이다.

앞에서 부터 뒤로가면서, 경우의 수는 포함하냐, 안하냐 뿐이다. 이를 DFS로 구현한다.

위와 같이 앞에서 부터 뒤로 방향성을 고정하고, 각 단계에서의 경우의 수를 파악하는 것이 중요하다

vector<int> v={1,2,3,54,8,34,54,70,46};
int sum=0;

int go(int idx, int sum) {
	if(idx==n) {
    	//검사하거나 등등해서 조건에 부합하면 return 1하고 아니면 return0 하는식으로 누적(카운트)
	}
	return go(idx+1, sum + v[idx]) + go(idx+1, sum); //sum에 고른 수들을 누적
}

• v: 입력받은 숫자들이 저장되어있는 벡터
• idx: 포함 or 불포함 여부를 결정할 인덱스
• idx가 n이되면 조합 1개가 완성된것이므로 적절한 로직을 수행한 후 결과에따라 return한다.

✍ B. 의사 결정 트리가 바로 안그려지는 경우 -> 앞에서부터 DFS로 완전 탐색

가능한 모든 합을 찾는 예시이다.

앞에서 부터 뒤로가면서, 경우의 수는 포함하냐, 안하냐 뿐이다. 이를 DFS로 구현한다.

vector<int> v;
int sum=0;

void go(int idx, int sum) {
	if(idx==n) {
  		//값 비교해서 최댓값 갱신하거나...등등의 로직
  	}
    go(idx+1, sum + v[idx]);
    go(idx+1, sum);
}

✍ C. 의사 결정 트리가 바로 그려지는 경우 -> DFS로 그래프를 완전 탐색

의사 결정 트리가 바로 그려지는 경우 -> DFS로 그래프 탐색하는 방식으로 풀어준다.

가능한 모든 경로를 찾는 예시이다.

그래프를 완전탐색하는 경우에는 원상복구 기능이 들어가야한다.
이전 탐색이 다음 탐색에 영향을 주면 안되기때문이다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[10];   // 인접 리스트
int visited[10];
vector<int> path;

void go(int here) {
    // 현재 경로 출력
    if(path.size() == n) {
    	for (int x : path) cout << x << " ";
    	cout << "\n";
        return;
    }   

    for (int there : adj[here]) {
        if (visited[there]) continue;

        visited[there] = 1;
        path.push_back(there);

        go(there);

        visited[there] = 0;      // 🔥 백트래킹
        path.pop_back();         // 🔥 백트래킹
    }
}

int main() {
    // 간단한 그래프
    adj[1] = {2, 3};
    adj[2] = {4};
    adj[3] = {4};
    adj[4] = {};

    // 시작 노드 1
    visited[1] = 1;
    path.push_back(1);

    go(1);
}

위의 코드를 보자.

노드에 방문할때마다 visited[]에 방문 표시 및 path 벡터에 원소로 노드를 추가해준다.
이후 go()를 통해 한번 더 재귀를 수행해서 위의 과정을 반복하다가,,

return이 되면 가장 최근에 방문한 노드를 visited[]에 미방문 처리하고, path 벡터에서도 삭제해줌으로써 다음 탐색에 주는 영향을 제거하고, 독립적으로 다음 경로를 탐색할 수 있게된다.

void go(int here) {
    // 현재 경로 출력
    if(path.size() == n) {
    	for (int x : path) cout << x << " ";
    	cout << "\n";
        return;
    }   

    for (int there : adj[here]) {
        if (visited[there]) continue;

        visited[there] = 1;
        path.push_back(there);

        go(there);

        visited[there] = 0;      // 🔥 백트래킹
        path.pop_back();         // 🔥 백트래킹
    }
}

이 go()의 코드 블럭을 외워두면 편할 것 같다.

✍ D. 의사 결정 트리가 바로 그려지는 경우 -> BFS로 그래프를 완전 탐색

의사 결정 트리가 바로 그려지는 경우 + 최소 비용 구하는 경우 -> BFS로 그래프 탐색하는 방식으로 풀어준다.

BFS코드 사용하면 BFS로 그래프 완전 탐색하는 것도 가능하다.

2. 완전 탐색에 적용하는 기술 1 - 백트래킹

상태를 원상복구하며 다른 경우 탐색하는 방식

3. 완전 탐색에 적용하는 기술 2 - 프루닝(pruning, 가지치기)

현재 탐색하는 경로가 조건에 부합할 가능성이 없으면 더이상 탐색하지 않고 되돌아가는 방식

기존 완전탐색은 불필요한 부분까지 전부 탐색해버리지만, 가지치기(Pruning)을 적용하면 알고리즘의 효율성이크게 향상된다.

#include <bits/stdc++.h>
using namespace std;

int n = 4, target = 10;
int arr[4] = {2, 4, 6, 8};
int cnt = 0;

void dfs(int idx, int sum) {

    // 🔥 Pruning: 이미 target 넘으면 더 볼 필요 없음
    if (sum > target) return;

    if (idx == n) {
        if (sum == target) cnt++;
        return;
    }

    dfs(idx + 1, sum + arr[idx]);
    dfs(idx + 1, sum);
}

int main() {
    dfs(0, 0);
    cout << "경우의 수: " << cnt << endl;
}

위와 같이 if (sum > target) return;을 통해서 이미 합이 target을 넘으면 더이상 해당 경로의 탐색을 진행하지않고 return해버린다.

4. 암기(최종 정리)

(1) 의사 결정 트리가 바로 그려지지 않는 경우 -> go(int idx, ~) 로 구현

• 순서
  1. 앞에서부터 뒤로가면서 각 단계에서 어떤 경우의 수 존재하는지 확인하기
  2. 앞에서부터 뒤로가면서 갱신할지 누적할지 결정하기
  3. 앞에서부터 뒤로가면서 인덱스 최대한 활용해서 구현하기

(2) 의사 결정 트리가 바로 그려지는 경우 -> dfs or bfs 로 의사 결정 트리 완전 탐색 구현

• 완전탐색만 하면 되는 경우
  1. 의사 결정 트리 떠올리기
  2. DFS or BFS 로 그래프 탐색 (백트래킹 잊지말기)
• 완전탐색으로 최소 비용(최단거리 OR 최소 시간) 찾아야하는 경우
  1. 의사 결정 트리 떠올리기
  2. BFS 로 그래프 탐색

(3) 그 외 -> 반복문이나 next_permutation 고려