[백준 1759] 암호 만들기 / 백트래킹

문제

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

1759번: 암호 만들기

나의 코드

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 16
 
using namespace std;
 
vector<char> vec;
char arr[MAX]; //문자열이므로 한칸 공백 필요
int C, L;
 
void Print() {
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i];
    cout << '\n';
    return;
}
 
void DFS(int cnt, int launch, int mo, int ja) {
    if (cnt == L) {
        if(mo >= 1 && ja >= 2)
            Print();
        return;
    }
 
    for (int i = launch; i < C; i++) {
        vec.push_back(arr[i]);
        if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            DFS(cnt + 1, i + 1, mo + 1, ja);
        else DFS(cnt + 1, i + 1, mo, ja + 1);
        
        vec.pop_back();
    }
}
 
int main(void) {
    cin >> L >> C;
 
    for (int i = 0; i < C; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + C);
    DFS(0, 0, 0, 0);
}
 

 

여기서 주의할 점 : DFS(cnt + 1, i + 1, mo + 1, ja); 대신에 mo++을 하면 나중에 return으로 돌아왔을 때 mo--을 해줘야하는 번거로움이 있으므로 재귀함수의 성질을 이용해서 DFS(cnt + 1, i + 1, mo + 1, ja);이렇게 코딩하는게 올바르다.

 

visited[] 배열은 어차피 launch가 그 다음 문자로 넘어가게 해주므로 필요가 없어진다!!