완전탐색

모든 경우의 수를 탐색하는 알고리즘으로, (순열 OR 조합) + 로직 으로 구현한다

(1) 사용하는 경우

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

(2) 구현 방법

✍ 반복문

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] << " ";
    }
}

✍ 재귀함수

재귀함수를 이용해 주어진 범위를 모두 검사히는 방법

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

✍ 재귀함수 구현 - 조합 누적

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한다.

✍ 재귀함수 구현 - 조합 검사

vector<int> v;
int sum=0;

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

완전탐색 - 그래프 완전탐색 (원상복구 기능)

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

#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()의 코드 블럭을 외워두면 편할 것 같다.

백트래킹

완전탐색 + 가지치기(프루닝)

가지치기 (Pruning)

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

기존 완전탐색은 불필요한 부분까지 전부 탐색해버리지만, 가지치기(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) {
    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;
}
✍ 백트래킹
#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해버린다.