백준 1759번 (C++)

문제 설명

 

문제 해결

수의 크기가 크지 않으면서, 모든 경우의 수를 탐색해야 하므로 완전 탐색인 DFS 문제임을 알 수 있다. 크게 어려운 문제는 아닌데, 처음에 visit 배열을 만들고,  for 문을 돌면서 DFS 함수에 들어가는 식으로 잘못 접근했다가 시간이 조금 걸렸다. 여기서는 그래프 탐색이 아니고 암호 선택의 문제이기 때문에, 해당 알파벳을 택한다 / 택하지 않는다의 두 가지 경우밖에 없다. 이 경우에 한해 재귀를 돌면 된다. 다시 방문할 일이 없으므로 visit 배열도 불필요하다. 

나는 아직도 재귀의 개념이 직관적으로 와닿지가 않는다. 그게 다양한 dfs 문제를 풀었음에도 불구하고 잘 막히는 이유인 것 같다. 문제를 풀 때 먼저 손으로 들어가기 전에 DFS의 정의를 어떻게 해야하는지를 확실히 생각하고 접근해야겠다.  암호의 기준을 판단하는 것은 check 함수를 따로 만들었고, string 함수중 find()를 사용해서 모음 여부를 판단하도록 했다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector <char> num;
int visit[16] = { 0, };
int l, c;
bool check(string str)
{
	string chk = "aeiou";
	int count = 0;
	for (int i = 0; i < str.length(); i++)
		if (chk.find(str[i]) != string::npos)
			count++; //즉, 모음이 있으면 
	if (count >= 1 && ((l - count) >= 2))
		return true;
	else
		return false;
}

void dfs(int idx, string str)
{
	if (str.length() == l) //종료 조건 
	{
		if (check(str))
			cout << str << "\n";
		return;
	}
	if (idx >= c)
		return;
	dfs(idx + 1, str + num[idx]); //선택 했을 때
	dfs(idx + 1, str); //선택 안했을 때 
}

int main(void)
{
	cin >> l >> c;
	for (int i = 0; i < c; i++)
	{
		char tmp;
		cin >> tmp;
		num.push_back(tmp);
	}
	sort(num.begin(), num.end());
	
	dfs(0, "");
	return (0);
}