[Baekjoon] 1759 - 암호 만들기 (C++)

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

알고리즘 분류는 백트래킹(backtracking)으로 되어 있지만, 입력으로 들어오는 데이터의 크기가 그렇게 크지 않기 때문에 완전 탐색(brute-force search)이나 그냥 모든 경우의 수를 DFS(depth-first search) 방법으로 다 확인하면서 해도 쉽게 해결할 수 있습니다. 하지만 그냥 문제 취지에 맞게 백트래킹을 이용해 풀어 보았습니다.

 

방법은 간단합니다. 먼저 입력으로 들어오는 문자들을 사전 순으로 정렬한 뒤, 앞에서부터 차례대로 각 문자에 대해 백트래킹을 적용해서 문자열을 만들어나가면 됩니다. 탐색 방법으로는 DFS를 사용했고, 재귀 함수를 이용해서 쉽게 구현할 수 있었습니다. 문자열의 길이가 문제에서 요구한 길이와 같아지면 모음과 자음의 개수를 확인해서 조건에 맞는 문자열만 출력하게끔 만드시면 됩니다.

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

using namespace std;

vector<char> charList;
int l, c;

bool isPossibleCode(const string& code)
{
	int vowel = 0;
	int consonant = 0;

	// 모음과 자음의 개수 계산
	for (char ch : code) {
		if (strchr("aeiou", ch)) vowel++;
		else consonant++;
	}

	// 모음이 1개 이상, 자음이 2개 이상일 경우 true 반환
	return vowel >= 1 && consonant >= 2;
}

void backtracking(const string& code, int index, int length)
{
	// 문자열이 완성될 경우 출력 후 함수 탈출
	if (length == l) {
		if (isPossibleCode(code)) cout << code << "\n";
		return;
	}

	// 가능한 경우의 수를 확인하면서 이미 만들어진 문자열에 문자를 하나씩 추가
	for (int i = index + 1; i <= c - l + length; i++) {
		backtracking(code + string(1, charList[i]), i, length + 1);
	}
}

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

	// 알파벳 소문자 입력
	for (int i = 0; i < c; i++) {
		char ch;
		cin >> ch;
		charList.push_back(ch);
	}

	// 사전 순으로 정렬
	sort(charList.begin(), charList.end());

	// 각 문자에 대해 백트래킹(backtracking) 적용
	for (int i = 0; i <= c - l; i++) {
		backtracking(string(1, charList[i]), i, 1);
	}

	return 0;
}