백준 1759: 암호 만들기

문제 요약

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

문제 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 백트래킹

문제 풀이

입력된 문자를 배열에 저장하여 정렬한 뒤, 0번 인덱스부터 DFS해 나가며, 재귀호출 횟수가 l이되면 출력 후 백트래킹 하면 된다.

재귀호출할 함수의 매개변수로는 탐색 인덱스, 카운트, 자음의 개수, 모음의 개수 이다.

DFS탐색을 하면서 ary배열에 탐색한 문자를 집어넣는다. 그리고 자음/모음에 따라 개수를 변화시키고, 카운트와 인덱스를 1증가시켜서 재귀호출하면 되는데, 카운트가 l이 되면 ary의 내용을 전부 출력한 뒤 재귀호출을 종료한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int l, c;
char ary[16] = {};
vector<char> v;

void dfs(int idx, int cnt, int consonant, int vowel) {
	if (cnt >= l) {
		if (consonant >= 2 && vowel >= 1) {
			for (int i = 0; i < l; i++)
				printf("%c", ary[i]);
			printf("\n");
		}
		return;
	}
	bool isVowel = false;
	for (int i = idx + 1; i < c; i++) {
		if (v[i] - 'a' == 0 || v[i] - 'a' == 4 || v[i] - 'a' == 8 ||
			v[i] - 'a' == 14 || v[i] - 'a' == 20) isVowel = true;
		else isVowel = false;
		ary[cnt] = v[i];
		dfs(i, cnt + 1, (isVowel ? consonant : consonant + 1), (isVowel ? vowel + 1 : vowel));
	}
}

int main()
{
	char in;
	cin >> l >> c;
	for (int i = 0; i < c; i++) {
		cin >> in;
		v.push_back(in);
	}
	sort(v.begin(), v.end());
	dfs(-1, 0, 0, 0);

	return 0;
}

후일담

매개변수를 4개로 할 것이 아니라, 자음 혹은 모음의 개수만 받아서 나머지 하나를 계산해도 괜찮을 것 같다. (전체 문자개수 - 모음의 개수 = 자음의 개수)