BOJ 1759번 암호 만들기

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

github : https://github.com/junho0956/Algorithm/blob/master/1759/1759/%EC%86%8C%EC%8A%A4.cpp

 

DFS 를 이용한 백트래킹을 구현하는 문제에 해당합니다.

 

주의할점은 자음과 모음의 갯수를 확인하는 것, 정렬을 해줘야 한다는 것입니다.

함수에 대한 설명은 주석처리해놓았고, 흐름대로 읽으시면 이해하기 쉽습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
#define endl "\n"
 
char arr[15];
int L, C;
 
void dfs(string str, int ja, int mo, int idx) {
    if (str.size() == L) {
        if (ja < 2 || mo < 1) return;
        cout << str << endl;
    }
 
    for (int i = idx; i < C; i++) {
        if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            dfs(str + arr[i], ja, mo + 1, i + 1);
        else
            dfs(str + arr[i], ja + 1, mo, i + 1);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> L >> C;
 
    for (int i = 0; i < C; i++) cin >> arr[i];
 
    sort(arr, arr + C);
 
    // 알아야하는 정보
    // 현재 스트링, 자음 갯수, 모음 갯수, 현재 인덱스
    dfs("", 0, 0, 0);
    return 0;
}