[BOJ] 백준 1759 암호 만들기 c++ (dfs, 백트래킹, 브루스포스)

문제 출처 : https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

풀이

dfs를 사용하여 해결한 문제이다.

 

dfs에서 알파벳을 하나씩 추가한뒤, L개가 되면 모음 조건 && 자음 조건을 확인해 처리하였다.

	str.push_back(v[now]);
	if(v[now] == 'a' || v[now] == 'e' || v[now] == 'i' || v[now] == 'o' || v[now] == 'u')
		vowel++;
	else conso++;

	if(str.length() == L){
		if(vowel >= 1 && conso >= 2)
			cout << str << '\n';
		return;
	}

여기서 배운점은, 자음의 수는 그냥 L - 모음의 수로 처리할 수 있었다...!

---

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int L, C;

// conso : 자음 개수, vowel : 모음 개수
void dfs(vector<char> v, int now, string str, int conso, int vowel){
	str.push_back(v[now]);
	if(v[now] == 'a' || v[now] == 'e' || v[now] == 'i' || v[now] == 'o' || v[now] == 'u')
		vowel++;
	else conso++;

	if(str.length() == L){
		if(vowel >= 1 && conso >= 2)
			cout << str << '\n';
		return;
	}

	for(int i = now + 1; i < C; i++)
		dfs(v, i, str, conso, vowel);
	return;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL);

	cin >> L >> C;
	vector<char> v(C);

	for(int i = 0; i < C; i++)
		cin >> v[i];		
	
	sort(v.begin(), v.end());

	for(int i = 0; i <= C - L; i++)
		dfs(v, i, "", 0, 0);

	return 0;
}