[백준 1062번 / C++] 가르침

이번 문제는 비트마스킹을 활용해서 완전 탐색을 하여 풀었다.

 

문제에서 n개의 문자열이 주어지는데 공통된 언어로는 "anta"로 시작되고, "tica"로 끝난다는 것이다. 

즉, 'a', 'n', 't', 'c', 'i' 이 단어를 배우지 못하면 어떤 단어도 읽지를 못한다. 그렇기 때문에 배우는 알파벳의 개수가 저 알파벳을 포함해서 최소 5개는 돼야 한다는 것이다. 

 

그렇기 때문에 alpa 라는 값에 최초 초기화해야할 숫자는 'a', 'n', 't', 'c', 'i'  이 단어를 가리키는 이진수의 값으로 나타내야한다. 

비트마스킹 활용법

그리고 dfs 를 돌게 되는데 여기서 중요한 점은 첫번째 인덱스를 돌다가 dfs를 돌 때는 그 인덱스 값을 파라미터 값으로 전달 해줘야한다. 즉, dfs 함수 안에서 또 for문이 동작하게 되는데 이때 i 는 다시 0부터 도는 것이 아니라 받아온 인덱스 값으로 시작해야한다. 

예를 들어 

a, b, c 나 c, b, a 는 똑같다는 것이다. 그렇기 때문에 이미 방문했던 알파벳은 더 이상 둘러보지 않는다는 것이 이 문제에 핵심이다. 이렇게 완전 탐색 문제에서는 n! 의 시간이 걸릴 수 있으니 이미 방문했던 곳은 둘러보지않고 건너뛰어야 시간초과가 발생하지 않는다. 이 점을 주의하고 문제 접근하자. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; 
int n, m; 
vector <int> v; 
int result = 0; 
void dfs(int alpa, int level, int index) {
	if (m == level) {
		int cnt = 0; 		
		for (int i = 0; i < n; i++) {		
			if ((alpa & v[i]) == v[i])cnt++; 
		}
		result = max(result, cnt); 
	}
	else {
		int x = 0; 
		for (int i = index; i < 26; i++) {	
			x = 1 << i; 
			if ((alpa & (x)))continue; 
			else {
				alpa |= x; 				
				dfs(alpa, level + 1, i); 
				alpa ^= x; 
			}
		}
	}
	return;
}
int main() {
	//a,n,t,i,c
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;	
	int alpa=0;
	alpa |= (1 << ('a' - 'a')); 
	alpa |= (1 << ('n' - 'a')); 
	alpa |= (1 << ('t' - 'a')); 
	alpa |= (1 << ('i' - 'a')); 
	alpa |= (1 << ('c' - 'a')); 
	vector <int> v1(n, 0); 
	for (int i = 0; i < n; i++) {
		string s = ""; 
		cin >> s; 
		for (int j = 0; j < s.size(); j++) {
			v1[i] |= 1 << (s[j] - 'a'); 
		}
	}
	if (m < 5) {
		cout << 0; return 0;
	}
	m = m - 5;
	v = v1; 
	dfs(alpa, 0, 0);
	cout << result; 
}

 

1062번: 가르침