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

문제 링크

1759번: 암호 만들기

 

풀이

백트래킹 문제

1. 알파벳을 입력받으며 모음인지, 자음인지 체크하여 pair로 넣는다. (모음은 1, 자음은 0)
2. 알파벳을 오름차순 정렬한 뒤, DFS 시작
3. 인자를 설명하자면 curIdx는 alpha에서 현재 인덱스, curString은 현재까지 만든 문자열, cnt는 모음의 개수이다.
   1. 만약 현재 문자열의 길이가 l과 같고, 모음이 1개 이상이고 자음이고 2개 이상이면 curString을 출력한다.
   2. alpha의 현재 인덱스 curIdx부터 시작해서 문자열(curString)을 만든다.
   3. DFS함수 재귀 호출을 통해 다음 인덱스의 문자를 더해 문자열을 만든다.

 

코드

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

void DFS(int curIdx, string curString, int cnt, int l, vector<pair<char, int>> &alpha)
{
    if (curString.size() == l && cnt >= 1 && l-cnt >= 2)
    {
        cout << curString << '\n';
        return;
    }
    for (int i = curIdx; i < alpha.size(); i++)
    {
        string tmp = curString;
        tmp += alpha[i].first;
        DFS(i+1, tmp, cnt + alpha[i].second, l, alpha);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int l, c;
    char tmp;

    cin >> l >> c;

    vector<pair<char,int>> alpha; // 모음은 1, 자음은 0으로 구별
    for (int i = 0; i < c; i++)
    {
        cin >> tmp;
        if (tmp == 'a' || tmp == 'e' || tmp == 'i' || tmp == 'o' || tmp == 'u')
        {
            alpha.push_back({ tmp, 1 });
        }
        else alpha.push_back({ tmp, 0 });
    }
    sort(alpha.begin(), alpha.end());

    DFS(0, "", 0, l, alpha);

}