백트래킹

14 May 2021

Reading time ~3 minutes

백트래킹

현재 상태에서 가능한 모든 후보군을 따라가며 탐색
오목 문제
- 상대편의 수를 예측하고 해당 위치에 놓았을 때, 잡히면 다시 돌아가서 다른 수를 고려해야함

N과 M (1) (백준)

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
https://www.youtube.com/watch?v=Enz2csssTCs&t=1391s&ab_channel=BaaarkingDog 보면서 이해

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int arr[10];
bool check[10];

void back_track(int k){
    if(k == m){
        for(int i=0; i<m; i++){
            cout << arr[i] << " ";  
        }
        cout << "\n";
        return;
    }

    for(int i=1; i<=n; i++){
        if(!check[i]){
            arr[k] = i;
            check[i] = true;
            back_track(k + 1);
            check[i] = false;
        }
    }
}
int main(){
    cin >> n >> m;

    back_track(0);

}

N과 M (2) (백준)

조합 알고리즘 문제 !!!
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 순열은 오름차순이어야 함

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int arr[10];
bool check[10];

void back_track(int index, int k){
    if(k == m){
        for(int i=0; i<m; i++){
            cout << arr[i] << " ";  
        }
        cout << "\n";
        return;
    }

    for(int i=index; i<=n; i++){
        if(!check[i]){
            arr[k] = i;
            check[i] = true;
            back_track(i + 1, k + 1);
            check[i] = false;
        }
    }
}
int main(){
    cin >> n >> m;

    back_track(1, 0);

}

조합을 DP로 구현하는 방법
- nCr = n-1Cr-1 + n-1Cr 성질 이용!

#include <iostream>
using namespace std;
int t, a, b, dp[31][31];
int cbn(int n, int r) {
	if(n == r || r == 0) return 1;
	if(dp[n][r]) return dp[n][r];
	return dp[n][r] = cbn(n - 1, r - 1) + cbn(n - 1, r);
}
int main() {
	cin >> t;
	while(t--) {
		cin >> a >> b;
		cout << cbn(b, a) << endl;
	}
}

부분 수열의 합 (백준)

(-2, 5, 3) 원소를 기준으로 상태트리를 만드는데, 차례대로 원소가 포함되었을 때는 오른쪽, 포함안되었을 때는 왼쪽으로 위치시켜 더해나감

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

using namespace std;

int N, sum;
vector<int> arr;

int cnt = 0;
void solve(int idx, int tmp) {

    if(idx == N){
        if (tmp == sum){
            cnt++;
        } 
        return;
    }
	

	solve(idx + 1, tmp);
	solve(idx + 1, tmp + arr[idx]);
}

int main() {
	
	cin >> N >> sum;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

	solve(0, 0);
	if(sum == 0){
        cnt --;
    }
	cout << cnt;

	return 0;
}

백준 가르침(1062)

‘a’ . ‘n’ , ‘t’ , ‘i’, ‘c’ 중에서 하나라도 배우지 못한다면 그 어떠한 단어도 읽지 못한다.
- 즉, 가르칠 수 있는 단어의 갯수인 K가 5보다 작은 값이 입력이 되면, 그 어떠한 단어도 읽지 못하게 된다.
핵심 : 배웠고, 배우지 못한 알파벳 처리
- bool 배열 사용
- a를 배웠다면, Alphabet[0] = true, c를 배웠다면, Alphabet[2] = true 이런식으로 알파벳을 숫자로 매칭시켜서 해당 인덱스의 값을 true로 바꿔주기
- a n t i c 이 5개의 알파벳은 시작부터 true로 설정
  - 이 5개의 알파벳 중 하나라도 배우지 못한다면 읽을 수 있는 단어가 없기 때문
- 이후 알파벳에서 K-5개를 조합으로 뽑아주면 됨
  - 조합인 이유는 a b c 3개의 알파벳을 알고 있을 때와 b c a 3개의 알파벳을 알고 있을 때 읽을 수 있는 단어는 똑같기 때문
    - 즉, 무슨 알파벳을 알고 있느냐에 따른 순서가 의미없기 때문에 조합으로 구현 가능

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;
int n, k, ans;
vector<string> v;
bool alpha[26];

int CanReadNum(){
    bool read;
    int cnt = 0;
    for(int i=0; i<v.size(); i++){
        read = true;
        string str = v[i];
        for(int j=0; j<str.length(); j++){
            if(!alpha[str[j] - 'a']){
                read = false;
                break;
            }
        }
        if(read == true){
            cnt++;
        }
    }
    return cnt;
}

void dfs(int idx, int cnt){
    if(cnt == k){
        ans = max(ans, CanReadNum());
        return;
    }

    for(int i=idx; i<26; i++){
        if(!alpha[i]){
            alpha[i] = true;
            dfs(i, cnt + 1);
            alpha[i] = false;
        }
    }
}
int main(){
    char c[5] = {'a', 'c', 'i', 'n', 't'};

    scanf("%d %d", &n, &k);
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        v.push_back(s);
    }

    alpha['a' - 'a'] = true;
    alpha['n' - 'a'] = true;
    alpha['t' - 'a'] = true;
    alpha['i' - 'a'] = true;
    alpha['c' - 'a'] = true;

    k = k-5;
    dfs(0, 0);
    cout << ans << '\n';
}

Algorithm