백준 1759 - 암호만들기 (백트래킹) c++

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

1759번: 암호 만들기

문제를 바라보면서 머릿속으로 해야하는 생각:

• 정렬된 문자열로 출력해야 한다 --> 입력 받으면 일단 정렬 한번 때려야 됨.
• 길이와 자음모음 갯수 조건이 있음 --> 출력하는 부분에서 확인해야 된다.
• 길이는 s.size()로. 자음모음 개수는? --> 저장해가면서!! 파라미터에다가.
• 여기까진 ok. 한번 어떤 알파벳을 골랐으면, 사전순서 이전에 있는 알파벳은 다음에 죽어도 못고른다. 그건 어떻게 구현하지? --> 고른 알파벳이 자음이냐 모음이냐에 따라 나누고 우선, 그다음엔 그 고른 알파벳보다 큰 인덱스의 알파벳만 탐색을 하게 백트래킹을 진행하면 된다.

솔직히 갓직히 이게 dfs문제인지는 감이 잘 안온다. 방문한 알파벳을 방문했다고 따로 표시는 안하니까..

이러한 일련의 과정들이 이제 backtracking()에 들어가 있다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int L,C;
char word[16];
 
void backtracking(int position, string s, int mo, int ja){
    int length = s.size();
    if(length==L){
        if(mo>=1&&ja>=2) {
            cout << s << "\n";
            return;
        }
    }
    else{
        for(int i=position; i<C; i++){
            if(word[i]=='a'||word[i]=='e'||word[i]=='i'||word[i]=='o'||word[i]=='u'){
                backtracking(i+1,s+word[i],mo+1,ja);
            }
            else{
                backtracking(i+1,s+word[i],mo,ja+1);
            }
        }
        return;
    }
 
}
 
int main(void){
    cin>>L>>C;
    for(int i=0; i<C; i++ ){
        cin>>word[i];
    }
    sort(word,word+C);
    backtracking(0,"",0,0);
}