BOJ 백준 C++ 1759번 암호만들기

 

문제 링크

1759번: 암호 만들기

 

DFS를 활용하는 문제, 우선 문자들을 모두 받아, 오름차순으로 정렬한 후에 DFS를 시작한다. Vector의 사이즈가 L에 도달할 때만 출력에 대해 검증(자음 2개이상, 모음 1개 이상)하고, 출력한다. 다음 재귀는 +1을 해서 호출한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int L, C;

vector<char> vec;
vector<char> tmpAns;

void DFS(int depth){

	int vali = false;
	int consonant = 0;
	int vowel = 0;

	int passwordSize = (int)tmpAns.size();

	if (passwordSize == L) {
		for (int i = 0; i < L; i++) {
			if (tmpAns[i] == 'a' || tmpAns[i] == 'e' || tmpAns[i] == 'i' || tmpAns[i] == 'o' || tmpAns[i] == 'u') {
				vowel += 1;
			}
			else {
				consonant += 1;
			}
		}

		if (consonant >= 2 && vowel >= 1) {
			vali = true;
		}
		else {
			vali = false;
		}

		if (vali) {
			for (int j = 0; j < L; j++) {
				cout << tmpAns[j];
			}
			cout << '\n';
			return;
		}
	}

	for (int t = depth; t < C; t++) {
		tmpAns.push_back(vec[t]);
		DFS(t + 1);
		tmpAns.pop_back();
	}
	return;


}

int main()
{
	cin >> L;
	cin >> C;

	for (int i = 0; i < C; i++) {
		char tmp;
		cin >> tmp;
		vec.push_back(tmp);
	}

	sort(vec.begin(), vec.end());
	DFS(0);

	return 0;
}