암호 만들기_백준1759_백트래킹

-문제-

-문제 접근-

위 문제의 요구사항을 크게 볼 때 조합 생성과 조건 검사 두 가지로 볼 수 있습니다.

1. 조합 생성

각 암호는 주어진 C개의 문자 중에서 L개를 선택한 조합을 말합니다.

2. 조건 검사

조건:

• 모음: 최소 1개 이상
• 자음: 최소 2개 이상
• 오름차순 정렬

모든 가능한 조합을 생성하고 문제의 조건을 검사하여 출력을 해야되는데 이러한 경우에 백트래킹을 사용하여 구현

할 수 있습니다.

 

3. 백트래킹

재귀 함수를 이용하여 인덱스 순서대로 문자를 선택하면서 조합을 구성하고 

기저 조건: 선택한 문자의 개수가 L개 

가 되었을 때 모음과 자음을 확인하며 조건 검사를 수행해야 합니다.

조건 검사 수행 후 만족했다면 문제에서 찾고자 한 가능성 있는 암호를 출력 할 수 있습니다.

 

-전체 코드-

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int L, C;
vector<char> arr; //주어진 문자 저장할 벡터
vector<char> result; // 선택된 조합(암호)을 저장할 벡터 

//모음 여부 판별
bool isVowel(char ch){
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}

bool count(int cnt){
    int vowelCnt = 0, consonantCnt = 0;
    for(int i = 0; i < cnt; i++){
        if(isVowel(result[i]))
            vowelCnt++; 
        else
            consonantCnt++; // 자음 카운팅
    }
    
    if(vowelCnt >= 1 && consonantCnt >=2 ) //문제의 조건 검사
        return true;
    else return false;
}

void BF(int index, int cnt){
    if(cnt == L){ //암호 완성시
        if(count(cnt)) { //조건 검사
            for(int i = 0; i < L; i++)
                cout << result[i]; // 조건 만족시 출력
            cout << "\n";
        }
        return ;
    }
    //순회하며 문자 선택
    for(int i = index; i < C; i++){
        result[cnt] = arr[i]; 
        BF(i + 1, cnt + 1); //재귀
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> L >> C;
    arr.resize(C);
    result.resize(L);
    
    for(int i = 0; i < C; i++){
        cin >> arr[i]; 
    }
    //사전적 출력 정렬
    sort(arr.begin(), arr.end()); 
    
    BF(0,0);
    
    return 0;
}

 

-코드 설명-

 

• 입력 및 초기화
  • L과 C를 입력받고, arr 벡터에 C개의 문자를 저장합니다.
  • result 벡터는 암호를 구성할 L자리 공간으로 미리 할당됩니다.
  • sort(arr.begin(), arr.end())를 통해 문자를 사전식으로 정렬하면, 선택되는 조합들도 자동으로 오름차순이 됩니다.
• 모음 판별 함수: isVowel
  • 전달된 문자가 a, e, i, o, u 중 하나이면 true를 반환합니다.
• 조건 검사 함수: count
  • 현재까지 선택된 조합(result)에서 모음과 자음의 개수를 세어,
    모음이 최소 1개 이상이고 자음이 최소 2개 이상이면 true를 반환합니다.
• 백트래킹 함수: BF
  • 재귀적으로 가능한 모든 L자리 조합을 생성합니다.
  • 기저 조건(cnt == L)에 도달하면, 현재 조합이 조건을 만족하는지 검사한 후 출력합니다.
  • for문을 통해 index부터 시작하여 문자를 선택하고,
    선택된 문자는 result[cnt]에 저장되며,
    재귀 호출로 다음 인덱스부터 선택을 이어갑니다.