백준 1062 가르침

가르침 (백준 1062)

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

bitset을 이용하여 각 문자의 알파벳을 나누어 저장하는 것까지는 완료하였으나
이후 풀이 과정 중 DFS를 전혀 떠올리지 못하였다

결국 블로그를 참조하였고
백트래킹과 재귀에 대한 연습이 재차 필요하단 것을 다시 느끼게 되었다

참고 : https://nanyoungkim.tistory.com/173

Code

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

//N 최대 50개
// word로 미리 '필요한 알파벳'들을 저장해둔다
int word[50];   
int N, K;

int maxi = 0;

//선택을 할수 있는 개수, 시작점 , 체크 여부
void DFS(int toPick, int start, int checked)
{
	// 재귀 종료
	if (toPick == 0)
	{
		// 그 알파벳들로 N개 단어 중 몇개 읽을 수 있는지 카운트해서 최대값 찾기
		// checked로 저장을 해둔 알파벳으로
		// word 배열을 돌면서 해당 checked와 비트 체크를 해준다
		// and 연산으로 자기 자신이 나왔다는 것은
		// 그 단어가 필요로 하는 알파벳을 모두 골랐다는 뜻
		int cnt = 0;
		for (int i = 0; i < N; i++) 
		{
			if ((word[i] & checked) == word[i])
			{
				cnt++;
			}
		}

		if (maxi < cnt)
		{
			maxi = cnt;
		}
		return;
	}

	for (int i = start; i < 26; i++) 
	{
		//방문 안 한 경우에만
		if ((checked & (1 << i)) == 0) 
		{
			// int 변수로 체크해주기
			checked |= (1 << i);
			DFS(toPick - 1, i, checked); // 재귀
			checked &= ~(1 << i); // 이후 풀어준다
		}

	}
}

int main() 
{
	int checked = 0;
	cin >> N >> K;

	string str;
	for (int i = 0; i < N; i++) 
	{
		cin >> str;

		int num = 0;
		for (int j = 0; j < str.length(); j++) 
		{
			num |= 1 << (str[j] - 'a');
		}
		word[i] = num;
	}

	//anta ~ tica 읽으려면 최소 a,n,t,i,c 5개 이상은 알고 있어야함
	if (K < 5) 
	{
		cout << 0;
	}  
	else if (K == 26)
	{
		cout << N;
	}
	else 
	{
		//a, n, t, i, c 를 이미 알고 있음을 초기화.
		checked |= 1 << ('a' - 'a');
		checked |= 1 << ('n' - 'a');
		checked |= 1 << ('t' - 'a');
		checked |= 1 << ('i' - 'a');
		checked |= 1 << ('c' - 'a');

		DFS(K - 5, 0, checked);
		cout << maxi;
	}

	return 0;
}

해결 아이디어

1. 알파벳 단어의 ‘개수’가 중요한 문제이다
   기본적으로 a c i n t 가 모든 단어에 포함되어야 하기에
   주어지는 k의 개수가 4개 미만이면 0을,
   반대로 k가 26개라면 모든 알파벳을 담을수 있으므로 n개를 출력
   
2. int로 비트마스킹을 할 변수를 선언 후,
   dfs(백트래킹)를 통해 ‘선택하지 않은’ 알파벳을 골라
   k-5개 까지 진행한다
   (위의 다섯 알파벳이 포함되어야 하기에, 선택할 수 있는 단어의 개수인 k에서
   5를 빼준다)
   
3. 모든 단어를 고른 경우(pickCount == 0)
   해당 알파벳이 들어간 int 형 변수와
   기존에 비트마스킹을 통해 만들어질 단어의 int 와 &연산자로 비교
   해당 연산을 통해 다시 단어가 나오는 경우,
   check 변수는 word[i]의 모든 알파벳 단어를 가지고 있는 상황이기에
   cnt++ 해준다
   
4. 가능한 모든 수를 돌면서 가장 높은 maxI를 출력한다