[백준/C++] 1759번: 암호 만들기

문제

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

---

문제 요약

알파벳 소문자로 이루어진 C개의 문자들이 주어졌을 때, 문자들을 조합하여 길이 L의 암호를 만들 수 있다.

 

만들 수 있는 모든 암호 경우의 수를 출력한다.

 

< 암호 규칙 >

1. 중복된 문자는 있을 수 없다.

2. 최소 1개의 모음(a, e, i, o u)으로 구성되어있다.

3. 최소 2개의 자음으로 구성되어있다.

4. 오름차순으로 정렬되어있다.

---

코드

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

using namespace std;

// C개 문자들로 만들어진 L자리 암호(문자열) 탐색
int L, C;

vector<char> chars;
vector<char> st;

// 현재 st가 조건에 부합하는지 확인
bool check() {
	int vowel = 0;
	
	// 현재 st의 모음 개수 판별
	for (int i = 0; i < L; i++)
	{
		if (st[i] == 'a' || st[i] == 'e' || st[i] == 'i' || st[i] == 'o' || st[i] == 'u') {
			vowel++;
		}
	}

	// 모음 수 1개 이상 && 자음 수 (= 전체 - 모음 개수) 2개 이상.
	if (vowel >= 1 && L - vowel >= 2) return true;

	return false;
}

// num번째 문자에 대해 백트래킹 탐색
void dfs(int num) {

	if (st.size() == L) { // 현재 st의 크기가 L 이고,
		if (check()) { // 조건에 부합한다면
			for (int i = 0; i < L; i++) {
				cout << st[i];
			}
			cout << "\n";
		}
		return;
	}
	
	// 그 다음 가능한 문자에 대해 탐색
	for (int i = num; i < C; i++) {
		st.push_back(chars[i]);
		dfs(i + 1);
		st.pop_back();
	}

	return;
}

int main() {
	
	// 입력
	cin >> L >> C;
	
	for (int i = 0; i < C; i++) {
		char ch;
		cin >> ch;
		chars.push_back(ch);
	}

	// 오름차순 정렬
	sort(chars.begin(), chars.end());

	// 첫번째 문자부터 백트래킹 탐색
	dfs(0);

	return 0;
}

---

코드 설명

1. 입력 받은 C개의 문자들을 chars 벡터에 저장하고, 오름차순으로 탐색을 하기 위해 정렬한다.

 

2. vector에 저장된 0번째 문자부터 하나씩 st 벡터에 저장하며 탐색을 시작한다.

+ st 벡터는 스택 역할을 한다.

 

3. st의 크기가 L이 되고, 암호 조건에 부합하다면 st 내 요소를 모두 출력하고 종료한다.

+ 탐색이 종료되었다면, 스택에서 요소를 제거하고, 루프를 통해 다음 요소에 대한 탐색을 진행한다.

---

고찰

 st에서 언제 요소를 넣고, 제거해야 하는지 헷갈렸다.

 

순서

1. i번째 문자를 st에 넣는다.

2. i + 1번째 문자에 대해 탐색한다.

3. 탐색이 종료되면 i번째 문자를 스택에서 제거한다.

 

=> 루프에 의해 가능한 다음 문자에 대해 진행한다.