[BOJ/C++] 1759 암호 만들기

 

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

풀이 

입력의 제한이 15 이기 때문에 브루트포스& 백트래킹을 사용하여 풀 수 있다고 생각하였고 실행에 옮겼다.

모음(vowel) 과 자음(consonant)의 계수의 제한이 있었다. 모음은 하나 이상 자음은 두 개 이상이다. 문제를 잘 읽고 풀도록 한다.

(깊이우선탐색)depth first search를 통한 백트래킹 기법을 사용하여 풀었다.

 

우선 입력받은 값 ex) a c b 를 사전 순으로 정렬하고 a b c 이 값들이 모음인지 자음인지 판별할 수 있는 boolean형 배열을 만들어

체크했다.

boolean형 배열 ex ) 1 0 0

그 후의 dfs를 사용하여 풀었다.

dfs함수 안에서는 지금 확인하는 캐릭터형이 자음인지 모음인지 확인하고 dfs 들어가면서 값을 증가시켜주는 식으로 하였다.

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n,m;
char *chars;
char res[15];
string answers;
bool *isVowel;
bool visited[15];
void dfs(int depths,int num,int vowel,int consonant){
    if(depths == m){ //return 구문
        if(vowel >= 1 && consonant >= 2){
            for(int i = 0 ; i < m;i++){
                answers += res[i]; 
            }
            answers += "\n";
        }
        return;
    }

    for(int i = num;i <n;i++){ // 재귀함수 구문
        if(!visited[i]){
            visited[i] = true;
            res[depths] = chars[i];
            if (isVowel[i])
            {
                dfs(depths + 1,i,vowel + 1,consonant);
            }
            else{
            dfs(depths + 1,i,vowel,consonant + 1);

            }
            
            visited[i] = false;
        }
    }
}
void solve(){
    cin >> m >> n;    
    chars = new char[n];
    isVowel = new bool[n];
    for (size_t i = 0; i < n; i++)
    {
        cin >> chars[i];
    }
    
    sort(chars,chars+n); // 사전순 정렬 

    for (size_t i = 0; i < n; i++) // 자음 모음 판별
    {
        if(chars[i] == 'a' || chars[i] == 'e' || chars[i] == 'i' || chars[i] == 'o' || chars[i] == 'u'){
            isVowel[i] = true;
        }
    }
    
    dfs(0,0,0,0);
    cout << answers;
    
    delete chars;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << "Hello World" << endl;
    solve();
    return 0;
}