1062 가르침

문자열 완전탐색 문제

DFS를 이용한 완전 탐색을 이용해 문제를 풀이한다

https://www.acmicpc.net/problem/1062

1. 문제

---

간단 설명

N개의 단어가 주어진다

K개의 알파벳을 사용할 수 있음

각 단어에서 모르는 알파벳이 있다면, 그 단어는 읽을 수 없음

즉, 한 문자열에서 모든 알파벳을 배운 적 있어야, 그 문자열을 읽을 수 있다!

2. 문제 분석

---

필요변수

단어 개수 N, 배울 글자 수 K

N개의 단어를 저장할 벡터 words

배운 알파벳들을 저장할 path

주의점

• 모르는 알파벳이 나왔다고 바로바로 학습해버리면 최대값을 구하지 못함
• 시간초과에 주의할 것
• 접두사 anta와 접미사 tica는 무조건 붙는다

알고리즘

1. N과 K를 입력받는다
	- K가 5보다 작다면 anta와 tica를 배우기에도 부족하므로 모든 단어를 읽을 수 없음. 0 리턴
	- K가 26이라면 모든 단어를 읽을수 있으므로 단어의 개수 N을 리턴
	
2. a, n, t, i, c 단어는 기본적으로 배운것으로 고려한다
	- 모든 단어에 접두사, 접미사로 들어감
	- 알파벳을 배웠다면 alpha 테이블에 표시해둔다 

3. DFS 조합을 이용해 나머지 배울 단어들을 고른다
	// DFS 탈출 조건
	3-1. 레벨이 K-5보다 크다면(이미 antic 알파벳 5개를 배웠으므로) 
		현재 생성한 path 문자열로 단어장에서 몇개를 읽을 수 있는지 확인한다
		3-1-1. 단어장의 각 단어를 앞 글자부터 끝까지 확인한다
		3-1-2. 만약 표기해둔 alpha 테이블에 0으로 표시된 안배운 단어가 있다면 못읽는 단어이므로 패스.
		3-1-3. 끝까지 읽을 수 있었다면 카운트 1 증가 시킨다
	
	// DFS 더 들어가는 부분
	3-2. 레벨이 K-5 보다 작다면 배울 알파벳을 골라 `path` 문자열에 추가한다
		3-2-1. 이미 배운 알파벳이라면 패스한다
		3-2-2. 알파벳을 배웠다면 alpha 테이블에 표시해둔다 
		3-2-3. DFS 조합을 다시 호출하여 레벨을 1 증가시키고, start부터 시작한다
		3-2-4. DFS를 나왔으므로 다시 초기화 해준다

Direct Access Table을 이용해 알파벳을 배웠는지 여부를 표시해두고,

각 문자열에서 알파벳이 나올때마다 바로 참조한다

만약 배운적 없는 알파벳이라면 못읽는 단어이므로 패스

(이전에 시도했던 문자열에서 알파벳을 find하고 erase 하는 방법보다 훨씬 빠름)

1. 처음 시도한 접근법

1. 학습할 수 있는 단어의 개수가 5개 미안이라면, anta, tica도 못읽으므로 0개 리턴
2. 단어장의 첫 단어의 첫 알파벳을 고르고, 모든 단어에서 이 알파벳을 지운다 (학습해서 읽을 수 있음)
4. 단어가 빈 문자열이 된다면 지우고 답을 1 더해준다(읽을수 있다)

그러나 이 방법은 첫 단어가 어떤 단어냐에따라 최적의 해를 구할 수 없었음

• 예제 3번의 테케 통과 못함

2. 두번째 시도한 접근법

DFS를 통해 배운 알파벳들로 조합을 만들고
조합으로 생성한 알파벳 각각을 단어에서 지워나간다
단어가 빈 문자열이 된다면 읽을 수 있음

세번째 테케는 통과했으나 시간초과…

DFS와 find, erase 탐색에 시간이 오래 걸린듯

3. 소스코드

---

// 정답 코드. 
#include <iostream>
#include <string>
#include <vector>


using namespace std;

int N, K;
int alpha[26]; // 배운 알파벳을 저장하는 배열
int answer = 0;
string path;
vector<string> words;

// 현재 생성한 path 문자열로 word에 몇개를 읽을 수 있는지 
int CheckWord(string path) {
	bool flag;
	int cnt = 0;
	// 이 문자가 배운적이 없는 문자인지를 체크

	for (string str : words) {
		flag = true;
		
		for (char ch : str) {
			// 문자열을 하나씩 지울 필요 없이 Direct Index Table 에서 배운 단어인지를 바로 확인한다
			if (alpha[(int)(ch - 'a')] == 0) {
				flag = false;
				break;
			}
		}
		if (flag == true) {
			cnt++;
		}
	}

	return cnt;
}

void DFS(int level, int start, string path) {
	if (level == K - 5) {
		answer = max(answer, CheckWord(path));
		return;
	}

	for (int i = start; i < 26; i++) {
		if (alpha[i] == 1) continue; // 이미 배운 단어
		
		char ch = (char)('a' + i);
		alpha[i] = 1; // 배웠음
		path.push_back((char)('a' + i));

		DFS(level + 1, i, path);

		alpha[i] = 0;
		path.pop_back();
	}

}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> K;

	if (K < 5) {
		cout << 0;
		return 0;
	}
	else if (K == 26) {
		cout << N;
		return 0;
	}

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

	// anta tica 를 읽기 위한 기본 5개 알파벳
	alpha[(int)('a' - 'a')] = 1;
	alpha[(int)('n' - 'a')] = 1;
	alpha[(int)('t' - 'a')] = 1;
	alpha[(int)('i' - 'a')] = 1;
	alpha[(int)('c' - 'a')] = 1;

	DFS(0, 0, "");
	cout << answer;

	return 0;
}

// 처음 시도한 접근법

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int N, K;
vector<string> words;
int answer = 0;

int main() {
	// input
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> K;

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

	// 단어가 5개 이하라면, anta, tica의 a n t i c 도 못읽으므로 0개 
	if (K < 5) {
		cout << 0;
		return 1;
	}
		
	while (K--) {
		if (words.empty()) break; // 알파벳은 더 배울수 있는데 더이상 단어가 없는경우

		// 첫 원소의 첫 알파벳을 학습한다.
		char ch = words[0][0];

		// 학습해서 읽을 수 있으므로 
		// 모든 단어에서 이 알파벳을 모두 제거한다		

		for (string& str : words) {
			while (str.find(ch) != string::npos)
			{
				str.erase(str.find(ch), 1);
			}

			for (auto it = words.begin(); it != words.end();) {
				if (*it == "") {
					it = words.erase(it);
					answer++;
				}
				else {
					++it;
				}
			}
		}		
	}

	cout << answer;

	return 0;
}

// 두번째 시도한 접근법

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, K;
vector<string> words;
int alpha[26];
int answer = 0;

// 배운 알파벳들의 리스트 path로, str을 만들수 있는지 체크 
// path에는 조합으로 생성한 알파벳들의 리스트가
// str에는 타겟 문자열이 들어있다
bool check_words(string path, string word) {
	for (int i = 0; i < 26; i++) {  // alpha도 포함해야 하므로 
		if (alpha[i] == 0) continue; // 안배운 단어
		
		char ch = (char)('a' + i);

		while (word.find(ch) != string::npos) {
			word.erase(word.find(ch), 1);
		}
		
		// 모두 지울 수 있었다면 OK
		if (word == "") {
			return true;
		}
	}
	return false;

}

void DFS(int level, int start, string path) {
	if (level == K - 5) {
		int cnt = 0;

		// 몇개를 만들수 있는지 체크한다
		for (string str : words) {
			if (check_words(path, str)) {
				cnt++;
			}
		}
		
		// 최대값과 비교후 갱신
		answer = max(answer, cnt);

		return;
	}

	// 알파벳을 하나씩 배우는 조합
	for (int i = start; i < 26; i++) {
		if (alpha[i] == 1) continue; // 이미 배웠다면 패스

		alpha[i] = 1;
		path.push_back('a' + i);

		DFS(level+1, i, path);

		path.pop_back();
		alpha[i] = 0;
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> K;

	// anta tica를 못읽음
	if (K < 5) {
		cout << 0;
		return 1;
	}
	// 모든 단어를 배워 모두 읽을 수 있음
	else if(K == 26){
		cout << N;
		return 2;
	}

	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		words.push_back(tmp.substr(4,tmp.length() - 8));
	}

	// antica는 기본으로 배운다
	alpha[(int)('a' - 'a')] = 1;
	alpha[(int)('n' - 'a')] = 1;
	alpha[(int)('t' - 'a')] = 1;
	alpha[(int)('i' - 'a')] = 1;
	alpha[(int)('c' - 'a')] = 1;
	
	DFS(0, 0, "");

	cout << answer;

	return 0;
}