[백준] #1759 암호만들기 - (BF)

dk문제

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

1759번: 암호 만들기

목표

주어진 알파벳으로 조건에 맞는 암호 생성

 

풀이

1. 조건을 확인할 수 있는 함수 생성

2. DFS를 사용하여 재귀함수 구현

내가 푼 방식: 정렬된 알파벳 배열에서 가장 작은 알파벳을 나타내는 인덱스를 사용하여 깊이우선탐색 수행

다른 코드: 비슷하지만 뭔가 더 전문적인거같음

 

코드

#1. 내코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int S, N;
//vect: 사용되는 알파벳저장, result: 알파벳으로 만드는 암호 저장
vector<char> vect;
vector<char> result;

//자음과 모음의 개수가 조건에 맞는지 확인
bool check(vector<char> result) {
    //자음개수와 모음개수 저장 변수
    int ja = 0;
    int mo = 0;
    //result 내부의 자음과 모음을 확인
    for (int i=0; i<result.size(); ++i) {
        if (result[i]=='a' || result[i]=='e' || result[i]=='i' || result[i]=='o' || result[i]=='u')
            mo++;
        else 
            ja++;
    }
    if (mo>=1 && ja>=2)
        return true;
    return false;
}
//result 출력 함수
void printString(vector<char> result) {
    for (int i=0; i<result.size(); ++i) {
        cout << result[i];
    }
    cout << '\n';
}
//메인기능을하는 함수
//smallest: 정렬된 알파벳에서 마지막에 쓰인 알파벳의 인덱스를 나타냄
//즉 가장 값이 낮은 알파벳
void makePassword(int smallest) {
    //result의 길이가 S와 같다면 조건을 확인한후 출력
    if(result.size() == S) {
        if (check(result))
            printString(result);
        return;
    }
    for (int i=smallest; i<N; ++i) {
        result.push_back(vect[i]);
        //i: 현재 쓰인 가장 작은 알파벳
        makePassword(i+1);
        result.pop_back();
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> S >> N;
    vect.resize(N);

    for (int i=0; i<N; ++i) {
        cin >> vect[i];
    }
    //정렬한후 함수호출
    sort(vect.begin(), vect.end());
    makePassword(0);
}

#2. 다른사람코드

#include <iostream>
#include <algorithm>

using namespace std;

char arr[16];
int N, C;
void dfs(int index, int ja, int mo, int cnt, string s) {
    if (cnt == N) {
        if (ja>=2 && mo>=1) {
            cout << s << '\n';
            return;
        }
    }
    if (index == C)
        return;
    if (arr[index]=='a' || arr[index]=='e' || arr[index]=='i' || arr[index]=='o' || arr[index]=='u')
        dfs(index+1, ja, mo+1, cnt+1, s+arr[index]);
    else 
        dfs(index+1, ja+1, mo, cnt+1, s+arr[index]);
    dfs(index+1, ja, mo, cnt, s);
}
int main() {
    cin >> N >> C;
    for (int i=0; i<C; ++i) {
        cin >> arr[i];
    }
    sort(arr, arr+C);

    dfs(0, 0, 0, 0, "");
}

 

 

참고

참고로 난 이렇게 사용한지 확인하는 배열도 만들었는데 풀고나서 보니 필요없는거였음

for (int i=smallest; i<N; ++i) {
     if (isPick[i] == false) {
         isPick[i] = true;
         result.push_back(vect[i])
         makePassword(i);
         result.pop_back();
         isPick[i] = false;
     }
 }