완전탐색(브루트포스), 백트래킹(back tracking) - 조합 재귀함수 구현코드, 원상복구

완전탐색은 모든 경우의 수를 탐색하는 것이고, 백트래킹은 완전 탐색을 기반으로 하되, 불필요한 연산을 좀 줄이는 것.

경우의 수는 순열과 조합 + 로직으로 풀린다. 이를 재귀 또는 반복문으로 구현할 수 있다.

원상복구 타이밍 잘 처리하기! 상태값이 그 다음 경우의 수에 영향미치지 않게 처리해주는 것

---

완전 탐색 (brute force, exhaustive key search)

모든 경우의 수를 탐색하는 알고리즘

순열or 조합 + 로직

보통 1억 미만까지는 컴퓨터를 믿고 넘겨라.

 

 

예제)

https://machineboy0.tistory.com/183

14502 : 연구소 - DFS, deep copy

벽을 세우는 경우의 수를 모두 탐색해야함.

다만 순서가 있다면 순열, 없다면 조합 요정도 수준.

---

완전탐색 구현 1 : 반복문을 활용한 완전탐색 (for, while)

//단순한 선형적 반복도 완전탐색

int main(){
	vector<int> v = {1,2,3,4,5};
    for(int i = 0; i < v.size(); i++){
    	if(v[i]==5){
        	cout << "야호\n";
        }
    }
}

 

 

예제) 

https://machineboy0.tistory.com/176

1436 : 영화감독 숌 - 숫자, 문자 변환 / 브루트 포스

666 부터 int_max까지 하나씩 돌리며 수를 찾는 것이므로 완전 탐색

---

완전탐색 구현 2 : 재귀함수 

 

반목문이 가능하면 무조건 반복문으로.

그 외에 너무 복잡하거나, 어떠한 행위를 반복하는데 매개변수만 수정해서 넘기면 될 것 같다? 그러면 재귀함수로

 

• 조합 or 순열 + DFS, BFS 등의 알고리즘
• 경우의 수 마다 생각해야하는 로직도 나온다.

예를 들어,

nC1,nC2,nC3 등 경우의 수를 생각해야한다면 재귀함수로 하는 것이 낫다. (비트마스킹은 추후에 배울 것)

---

예제 1)

승철이는 도쿄 상공의 구름 위에 올라가 있다. 이 구름은 그대로 내버려두면 땅으로 떨어져 100만명의 사상자가 발생한다.

구름을 멈추는 방법은 구름의 특정 위치에 합이 소수가 되는 n개의 요석을 꽂으면 된다.

총 몇 개의 경우의 수가 있는지.

 

입력)

10

24 35 38 40 49 59 60 67 83 98

 

---

예제 2)

N개의 자연수가 주어질 때

여기서 몇 개의 숫자를 골라 합을 mod11 했을 때 나오는 가장 큰 수를 구하라.

#include <bits/stdc++.h>
using namespace std;
int n,temp, ret;
vector<int> v;
const int mod = 11;
int cnt = 0;



void go(int idx, int sum){

    if(idx == n){       //재귀함수는 기저사례가 중요
        ret = max(ret, sum %mod);
            cnt++;
            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";
    cout << cnt << "\n";
}

---

백트래킹 (back tracking)

 

완전 탐색을 하되, 할 필요 없는  것들은 가지치기

최대한 불필요한 탐색을 피하는 것.

위의 문제에서 불필요한 연산을 좀 줄여보자.

 

예제 2)

N개의 자연수가 주어질 때

여기서 몇 개의 숫자를 골라 합을 mod11 했을 때 나오는 가장 큰 수를 구하라.

#include <bits/stdc++.h>
using namespace std;
int n,temp, ret;
vector<int> v;
const int mod = 11;
int cnt = 0;

void go(int idx, int sum){

//	최대는 10이므로 10에 이미 충족했다면 나머지연산은 불필요
    if(ret == 10) return;

    if(idx == n){       //재귀함수는 기저사례가 중요
        ret = max(ret, sum %mod);
            cnt++;
            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";
    cout << cnt << "\n";
}

---

완전탐색과 원상복구

완전탐색하며 변화를 주고 원상복구를 해야하는 경우,

즉, 상태값이 그 다음 경우의 수에 반영되지 않도록 원상 복구를 해야하는 경우

 

https://machineboy0.tistory.com/183

14502 : 연구소 - DFS, deep copy

---

예제 1)

아래와 같이 노드가 이어저 있을 때, 탐색한 정점이 3개이면 출력하라.

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

int n, visited[4];
vector<int> v;
vector<int> adj[4];

void print(){
    for(int i : v) cout << char(i + 'A') << " ";
    cout <<'\n';
}

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();		//빼자
    }
}


int main(){
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[1].push_back(2);
    adj[2].push_back(1);

    adj[1].push_back(3);
    adj[3].push_back(1);
 
    visited[0] = 1;
    v.push_back(0);
    go(0);
    return 0;
}

 

원복의 기본꼴

go(int here){
	visited[there] = 1;	// 방문 처리
    go(there);
    visited[there] = 0;	// 방문 처리 지우기
}

---

예제 2)

홍철이는 각 칸마다 코인이 있는 3*3맵 위에 서있고, (0,0) 지점에서, (2,2)로 가면서 코인을 얻으려고 한다.

홍철이는 상하좌우로 이동할 수 있다. 각 칸에 있는 코인의 수는 아래와 같다.

코인을 모으는 모든 경우의 수를 출력하여라.

 

{10,20,21}

{70,90,12}

{80,110,120}

 

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

const int n = 3;
int a[3][3] = {
    {10,20,21},
    {70,90,12},
    {80,110,120}
};

int visited[3][3];

const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};

vector<int> v;

void print(){
    for(int i : v) cout << i <<" ";
    cout <<'\n';
}

void go(int y, int x){
    if(y==n-1 && x == n-1){
        print();
        return;
    }

    for(int i = 0; i <4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny <0||nx<0||ny>=n|| nx>=n) continue;
        if(visited[ny][nx]) continue;

        visited[ny][nx] = 1;    //방문 처리
        v.push_back(a[ny][nx]); // 넣고

        go(ny,nx);              // 원하는 거 실행하고

        visited[ny][nx]= 0;     // 방문 처리 취소
        v.pop_back();           // 빼고
    }
}

int main(){
    visited[0][0] = 1;
    v.push_back(a[0][0]);
    go(0,0);
    return 0;
}

 

딱 바꿔준 것만 교체하는 그런 로직 생각해야함.