[백준] 1062-가르침(C++)

문제링크:https://www.acmicpc.net/problem/1062

1062번: 가르침

 

브루트 포스문제이고 dfs를 통해서 구현해야하는 문제였습니다.

 

기본적인 구현은 dfs를 통한 재귀로 구현해주시면 됩니다.

문제는 시간초과문제입니다.

 

확인해야하는 알파벳은 26-5 =21개입니다. 

이때 매번 15-8 =7개 * 50개 의 알파벳을 확인해주는 재귀이기 때문에 가지치기를 잘해야하는 문제였습니다.

 

가지치기

•  1. k <5, k==26의 극단값 처리 (엄연하게 백트래킹 가지치기는 아니죠)
•  2. dfs에 alpha 변수를 통해서 알파벳 중에서 k-5개를 선택할 때 중복이 안 생기도록 만들기 (이게 백트래킹의 핵심입니다.)
•  3. set 컨테이너를 통해서 arr안에 들어가는 알파벳의 중복을 제거했습니다. (안해도 통과는 됩니다.)

정답 코드입니다. 

#include <algorithm>
#include <iostream>
#include <string>
#include <set>
using namespace std;
bool visited[26] = { 0 };
set<char> arr[51];
int n = 0, k = 0, result = 0;

void dfs(int alpha, int cnt) {
	if (cnt == (k - 5)) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			bool jud = true;

			for (auto it = arr[i].begin(); it != arr[i].end(); it++) {
				if (visited[*it - 'a'] == 0) {
					jud = false;
					break;
				}
			}
			
			if (jud == true)
				cnt++;
		}
		 result = max(result,cnt);

		return;
	}

	for (int i = alpha; i < 26; i++) {

		if (visited[i] == 0) {
			visited[i] = 1;
			dfs(i,cnt + 1);
			visited[i] = 0; 
		}
	}

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	visited['a' - 'a'] = 1;
	visited['c' - 'a'] = 1;
	visited['i' - 'a'] = 1;
	visited['t' - 'a'] = 1;
	visited['n' - 'a'] = 1;

	for (int i = 0; i < n; i++) {
		string v;
		cin >> v;
		for (int j = 0; j < v.size(); j++) {
			if (v[j] != 'a' && v[j] != 'c' && v[j] != 'i' && v[j] != 't' && v[j] != 'n') {
				arr[i].insert(v[j]);
			}
		}
			
	}
	

	if (k < 5) {
		cout << 0 << '\n';
		return 0;
	}
	else if (k == 26) {
		cout << n << '\n';
		return 0;
	}
	dfs(0,0);

	cout << result << '\n';
}