C - [백준 1759] 암호 만들기

참고 포스트

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 9663] N-Queen (feat. 백트래킹, DFS)

 

 

예제 입력 1 

4 6
a t c i s w

예제 출력 1 

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

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

---

BOJ 1759번: 암호 만들기

문제의 핵심은 알파벳 C개 중 L개의 알파벳으로 구성된 암호를 생성하는 것입니다. 암호는 다음 조건을 만족해야 합니다:

1. 모음(a, e, i, o, u)이 최소 1개 포함되어야 합니다.
2. 자음은 최소 2개 포함되어야 합니다.
3. 알파벳은 사전순으로 정렬된 순서로 나타나야 합니다.

입력으로는 L(암호의 길이)와 C(주어진 알파벳의 개수)가 주어지며, 가능한 모든 암호를 출력하는 것이 목표입니다

 

---

 

Checkpoint

 

기존의 N과 M 문제(https://rnasterofmysea.tistory.com/69)가 숙달 되었다면 해당 문제의 요구조건만 충족하면 쉽게 해결할 수 있던 문제 였다.

 

※ 문제의 요구조건

1. 모음(a, e, i, o, u)이 최소 1개 포함되어야 합니다.
2. 자음은 최소 2개 포함되어야 합니다.
3. 알파벳은 사전순으로 정렬된 순서로 나타나야 합니다.

3번 조건일 경우,

 

입력 후 정렬 알고리즘을 사용하며 미리 입력값을 정렬해놓고 백트래킹을 설계하면 해결이 가능하다.

 -> 배열의 최대값인 15인 작은 배열이기 때문에 선택정렬을 사용하여 간단하게 구현하였다.

 

1,2번 조건일 경우, 

 

자음(vowels), 모음(consonants)을 DFS 함수 내에서 카운팅하고 기저 조건(base case), 즉 DFS가 리프노드에 도달했을 때, 다시 말해 암호 생성이 완료되어 출력할 때, 자음이 2개 이상일 때, 모음이 1개 이상일 때 출력하는 조건을 추가하면 된다.

 

if(depth == L && vowels >= 1 && consonants >= 2){
        for(int i = 0; i < L; i++){
            printf("%c", arry[i]);
        }
        printf("\n");
        return;
    }

---

 

구현 코드

/*
BOj_1759_암호만들기
https://www.acmicpc.net/problem/1759
*/

#include <stdio.h>
#define MAX 15
int L, C;
char input_arry[MAX+1];
char arry[MAX+1];
int visited[MAX];

void selectSort(int C){
    char min = 0;
    for(int i = 0 ; i < C - 1; i++){
        min = i;
        for(int j = i+1 ; j <C; j++){
            if(input_arry[min] > input_arry[j]){
                min = j;
            }
        }
        if(min != i){
            char temp = input_arry[i];
            input_arry[i] = input_arry[min];
            input_arry[min] = temp;
        }
    }
}

int isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

void dfs(int depth , int vowels, int consonants){
    if(depth == L && vowels >= 1 && consonants >= 2){
        for(int i = 0; i < L; i++){
            printf("%c", arry[i]);
        }
        printf("\n");
        return;
    }
    
    for(int i = 0; i < C; i++){
        if(!visited[i]){
            if (depth > 0 && arry[depth - 1] > input_arry[i]) {
                continue;
            }

            arry[depth] = input_arry[i];
            visited[i] = 1;

            if (isVowel(input_arry[i])) {
                dfs(depth + 1, vowels + 1, consonants);
            } else {
                dfs(depth + 1, vowels, consonants + 1);
            }

            visited[i] = 0;
        }
    }
    
}

int main() {
    scanf("%d %d", &L, &C);
    for(int i = 0 ; i < C ; i ++){
        scanf(" %c", &input_arry[i]);
    }

    selectSort(C);

    dfs(0,0, 0);
    
    return 0;
}

 

---

코드 풀이

1. 정렬: 입력된 알파벳 배열을 사전순으로 정렬하여 암호를 생성할 때 순서를 유지합니다.
2. 백트래킹(DFS): 가능한 모든 조합을 탐색하며 조건에 맞는 암호를 출력합니다.
3. 조건 검사: 모음과 자음의 개수를 추적하여 조건을 만족하는지 확인합니다.

 

1. selectSort 함수

void selectSort(int C){
    char min = 0;
    for(int i = 0 ; i < C - 1; i++){
        min = i;
        for(int j = i+1 ; j <C; j++){
            if(input_arry[min] > input_arry[j]){
                min = j;
            }
        }
        if(min != i){
            char temp = input_arry[i];
            input_arry[i] = input_arry[min];
            input_arry[min] = temp;
        }
    }
}

• 선택 정렬 알고리즘을 사용하여 알파벳 배열을 사전순으로 정렬합니다.
• 사전순 정렬은 암호 생성 시 정렬 상태를 유지하기 위해 필요합니다.

 

2. isVowel 함수

int isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

• 입력된 문자가 모음인지 여부를 확인하는 함수입니다.

 

3. dfs 함수 (백트래킹)

void dfs(int depth , int vowels, int consonants){
    if(depth == L && vowels >= 1 && consonants >= 2){
        for(int i = 0; i < L; i++){
            printf("%c", arry[i]);
        }
        printf("\n");
        return;
    }
    
    for(int i = 0; i < C; i++){
        if(!visited[i]){
            if (depth > 0 && arry[depth - 1] > input_arry[i]) {
                continue;
            }

            arry[depth] = input_arry[i];
            visited[i] = 1;

            if (isVowel(input_arry[i])) {
                dfs(depth + 1, vowels + 1, consonants);
            } else {
                dfs(depth + 1, vowels, consonants + 1);
            }

            visited[i] = 0;
        }
    }
}

• depth: 현재 선택된 알파벳의 개수를 추적합니다.
• vowels, consonants: 모음과 자음의 개수를 각각 세어 조건을 검사합니다.
• 조건:
  1. 선택된 알파벳 개수(depth)가 L과 같아야 합니다.
  2. 모음 개수는 1개 이상, 자음 개수는 2개 이상이어야 합니다.
• 반복문을 통해 아직 선택되지 않은 알파벳을 선택하며 재귀 호출을 진행합니다.
• 조건에 맞지 않는 경우를 제외(continue)하여 불필요한 탐색을 줄입니다.

 

4. main 함수

int main() {
    scanf("%d %d", &L, &C);
    for(int i = 0 ; i < C ; i ++){
        scanf(" %c", &input_arry[i]);
    }

    selectSort(C);

    dfs(0,0, 0);
    
    return 0;
}

• 입력받은 알파벳 배열을 정렬하고, 백트래킹을 시작합니다.
• 결과적으로 조건을 만족하는 모든 암호를 출력합니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.