백준 문제 링크 : 1759번: 암호 만들기 (acmicpc.net)
백준 1759번 암호만들기 문제 사진
문제 요약
입력 값 : L(문자열 길이), C(문자 갯수), Ch x C(사용 가능한 문자[알파벳])
- 입력 받은 문자를 이용해 문자열을 구성한다.
- 생성한 문자열에는 최소한 1개의 모음과 2개의 자음이 포함되어야 한다.
- 문자열의 문자들은 사전 순서대로 배치되어야만 한다.(조건에 맞는 문자열 : abc, 조건에 맞지 않는 문자열 : bac)
- 생성된 문자열들을 사전 순서대로 출력 되어야 한다.
문제 풀이 과정
이 문제는 입력된 문자들을 활용하여 L만큼의 길이를 가지는 사전 순서대로 배열된 문자열을 생성하는 문제입니다. 이때 자음과 모음이 각각 2개, 1개 반드시 포함되어야 하죠. 그리고 이렇게 생성된 문자열을 사전 순서대로 출력해야 합니다.
저는 이번 문제를 아래와 같은 순서로 풀었습니다.
먼저 백트래킹을 이용하여 생성 가능한 문자열들을 생성합니다. 사용한 문자열들은 is_selected 배열에 방문 표시를 하여 중복하여 선택되지 않도록 만듭니다.
이때 자음과 모음 여부를 판단하고 그 갯수를 변수에 저장하여 넘겨주는 것으로 조건에 맞지 않는 문자열이 생성될 가능성이 있는 경우 가지치기 합니다.(create_password의 vowel과 consonant 변수)
이를 위해 is_vowel이라는 함수를 생성하여 입력 받는 문자가 모음인지 판별합니다. 이때 모음은 반모음 등은 포함하지 않는 [a, e, i, o, u]만 의미합니다.
이렇게 생성하는 문자열이 요청 길이에 도달할 경우 해당 문자들을 붙여 문자열을 만들고 문자열을 우선순위 큐에 오름차순으로기입하여 자동으로 정렬시킵니다.
위 과정이 모두 종료되면 우선순위 큐가 빌 때까지 문자열을 출력하여 줍니다.
코드는 아래와 같습니다.
#include <iostream>
#include <queue>
using namespace std;
//모음 모음
char vowel[5]={
'a',
'e',
'i',
'u',
'o'
};
//입력 값
int l,c;
//입력받은 문자들
vector<char> characters;
//결과
vector<char> result_characters;
//방문여부 표시
vector<bool> is_selected;
//결과값 저장용 우선순위 큐
priority_queue<string,vector<string>,greater<string>> result_queue;
bool is_vowel(char input){
for (int i = 0;i < 5; i++) {
if (vowel[i] == input) {
return true;
}
}
return false;
}
//백트래킹
void create_password(int start,int length,int vowel,int consonant){
//조건 합치 판별
if (l - consonant < 1|| l - vowel < 2) {
return;
}
//길이에 도달하면 문자열 생성 후 큐에 기입
if(length == l) {
char charset[l];
for (int i = 0;i < l; i++) {
charset[i] = result_characters[i];
}
result_queue.push(charset);
return;
}
for (int i = 0;i < c;i++) {
if(is_selected[i]) continue;
if(length - 1 >= 0) if(result_characters[length - 1] > characters[i]) continue;
bool is_v = is_vowel(characters[i]);
is_selected[i] = true;
result_characters[length] = characters[i];
create_password(i,length + 1,is_v ? vowel + 1 : vowel,is_v ? consonant : consonant + 1);
is_selected[i] = false;
}
}
int main()
{
cin >> l >> c;
is_selected = vector<bool>(l,false);
result_characters = vector<char>(l,0);
for (int i = 0;i < c;i++) {
char ch;
cin >> ch;
characters.push_back(ch);
}
//비밀번호 생성
create_password(0, 0, 0, 0);
//우선순위 큐에서 값 출력
while (!result_queue.empty()) {
cout << result_queue.top() << "\n";
result_queue.pop();
}
return 0;
}백트래킹 알고리즘을 사용한 다른 문제의 경우 아래 카테고리에서 찾아보실 수 있습니다.