BOJ 1759 암호 만들기

알고리즘 분류 : 수학, 브루트포스 알고리즘, 조합론, 백트래킹

 

전형적인 백트래킹문제이다.

모든 경우의 수에 대해서 탐색하되 조건이 맞을 경우에만 출력하면 된다.

 

입력으로 주어진 알파벳들을 오름차순으로 정렬하고

맨 앞부터 하나씩 골라서 길이가 l인 암호가 만들어졌을 때,

모음이 한 개 이상이고, 자음이 2개 이상이라면 출력한다.

 

재귀식으로 탐색하는 법이 코드짜기가 편하다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int l, c;
char a;
vector<char> v, st;
set<char> vw = { 'a', 'e', 'i', 'o', 'u' };

void dfs(int x, int vowel) {
	if (st.size() == l) {
		if (vowel && (l - vowel > 1)) {
			for (int i = 0; i < l; i++)
				cout << st[i];
			cout << '\n';
		}
	}
	else {
		for (int i = x; i < c; i++) {
			st.push_back(v[i]);

			dfs(i+1, vowel + (vw.find(v[i]) != vw.end()));

			st.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> l >> c;
	for (int i = 0; i < c; i++) {
		cin >> a;
		v.push_back(a);
	}

	sort(v.begin(), v.end());

	dfs(0, 0);

	return 0;
}