백준 1759번 암호 만들기 C++

🔷 백준 1759번 – 암호 만들기 (C++)

---

문제 설명

문제

• 암호는 서로 다른 L개의 알파벳 소문자로 구성됩니다.
• 반드시 최소 1개의 모음(`a`, `e`, `i`, `o`, `u`)이 포함되어야 합니다.
• 반드시 최소 2개의 자음이 포함되어야 합니다.
• 알파벳은 사전 순으로 정렬되어 있어야 합니다.

주어진 C개의 문자 중에서 위 조건을 만족하는 모든 암호를 출력하는 프로그램을 작성합니다.

---

입력

L C
C개의 알파벳 (공백 구분)

출력

조건을 만족하는 모든 암호 (한 줄에 하나씩)

---

테스트케이스

예제 입력

4 6
a t c i s w

예제 출력

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

---

구체적 설명

이 문제에서 주어진 문자를 이용하여 만들 수 있는 모든 길이 L의 조합을 찾아야 하며, 그 조합이 모음 1개 이상 + 자음 2개 이상 조건을 만족하면 출력합니다. 예를 들어,

• `a c i s` → 모음(`a`,`i`) 2개, 자음(`c`,`s`) 2개 → 조건 만족 (출력)
• `a c s w` → 모음 1개, 자음 3개 → 조건 만족 (출력)
• `c s t w` → 모음 없음 → 조건 불만족 (미출력)

---

📌 아이디어

1. DFS(Depth-First Search, 깊이 우선 탐색)란?

DFS란 쉽게 말해,

• 모든 경우를 빠짐없이 탐색할 수 있는 방법입니다.
• 어떤 문제를 풀 때 가능한 모든 방법을 빠짐없이 하나씩 확인할 때 사용합니다.

2. DFS로 이 문제를 어떻게 풀 수 있을까요?

지금 우리가 가지고 있는 문자는 다음과 같습니다.

{ a t c i s w }

이 문자들에서 조건(모음≥1, 자음≥2)을 만족하면서, 길이 4개인 암호를 찾아야 합니다. 이것을 DFS로 풀 때 가장 중요한 아이디어는 "각각의 문자를 하나씩 살펴보면서 선택할지 안 할지를 매번 결정하는 것"입니다. 쉽게 말해, 다음과 같은 생각을 매 문자마다 반복하는 겁니다.

• 이 문자를 선택한다.
• 이 문자를 선택하지 않는다.

모든 문자를 이렇게 선택하거나 선택하지 않으면서, 조건을 만족하는 길이 4의 암호를 찾습니다.

---

📌 DFS가 실제로 진행되는 과정 (아주 자세히)

처음엔 아무것도 선택하지 않았습니다.

📍 [시작]

{ a t c i s w }

이 상태에서 첫 번째 문자 `a`를 볼 차례입니다. 여기서 우리는 두 가지 길을 생각할 수 있습니다.

• `a`를 선택할 수 있고 (선택)
• `a`를 선택하지 않을 수도 있습니다 (비선택)

각각의 경우를 따로 살펴보겠습니다.

---

📍 [1-1 단계] `a`를 선택 ✅

{ [a] t c i s w }
현재 선택된 문자: a
(모음1, 자음0, 길이1)

이제 다음 문자인 t를 볼 차례입니다. 이 상태에서 t를 선택하거나 선택하지 않을 수 있습니다.

• 선택한 경우: `[a t]`
• 선택하지 않은 경우: `[a]`

---

📍 [2-1 단계] `t`를 선택 ✅ (`a`를 선택한 상태에서)

{ [a] [t] c i s w }
현재 선택된 문자: a t
(모음1, 자음1, 길이2)

이제 다음 문자인 c를 볼 차례입니다.

• 선택하면: `[a t c]`
• 선택하지 않으면: `[a t]`

---

📍 [3-1 단계] `c`를 선택 ✅ (`a t` 선택 상태에서)

{ [a] [t] [c] i s w }
현재 선택된 문자: a t c
(모음1, 자음2, 길이3)

이제 다음 문자인 i를 볼 차례입니다.

• 선택하면: `[a t c i]`
• 선택하지 않으면: `[a t c]`

---

📍 [4-1 단계] `i`를 선택 ✅ (`a t c` 선택 상태에서)

{ [a] [t] [c] [i] s w }
현재 선택된 문자: a t c i
(모음2, 자음2, 길이4)

길이가 4개가 되었으므로 이제 조건을 체크합니다.

• 모음 최소1, 자음 최소2 충족? ✅ 예, 만족합니다.
• 조건 만족 → 🔔 출력: `"atci"`

✅ 암호를 찾았으므로 이 뒤(s,w)는 더 확인하지 않고, 이제 뒤로 되돌아갑니다. (이것을 백트래킹(Backtracking)이라고 합니다.)

---

📍 [백트래킹 #1] 다시 `i`로 돌아감 ⬅️🔙

아까 상태로 돌아가 `i`를 선택하지 않은 경우를 진행해야 합니다.

{ [a] [t] [c] i s w }
현재 선택된 문자: a t c
(모음1, 자음2, 길이3)

• 이제 다음 문자 `s`를 선택하거나 선택하지 않습니다.

---

📍 [4-2 단계] `s`를 선택 ✅ (`a t c` 선택, `i` 비선택 상태)

{ [a] [t] [c] i [s] w }
현재 선택된 문자: a t c s
(모음1, 자음3, 길이4)

길이 4, 조건 확인:

• 모음 최소1, 자음 최소2 충족? ✅ 네, 만족합니다.
• 조건 만족 → 🔔 출력: `"atcs"`

✅ 암호를 찾았으므로 다시 뒤로 되돌아갑니다.

---

📍 [백트래킹 #2] 다시 `s`로 돌아가 비선택으로 변경 ⬅️🔙

{ [a] [t] [c] i s w }
현재 선택된 문자: a t c
(모음1, 자음2, 길이3)

이제 다음 문자 `w`를 선택하거나 선택하지 않습니다.

---

📍 [4-3 단계] `w`를 선택 ✅ (`a t c` 선택, `i s` 비선택 상태)

{ [a] [t] [c] i s [w] }
현재 선택된 문자: a t c w
(모음1, 자음3, 길이4)

길이 4, 조건 확인:

• 모음 최소1, 자음 최소2 충족? ✅ 네, 만족합니다.
• 조건 만족 → 🔔 출력: `"atcw"`

✅ 다시 뒤로 되돌아갑니다.

---

📍 [백트래킹 #3] w까지 끝나면 다시 이전(c)로 되돌아감 ⬅️🔙🔙🔙

{ [a] [t] c i s w }
현재 선택된 문자: a t
(모음1, 자음1, 길이2)

이제 c를 비선택 상태로 바꾸고, 다음 문자(i)로 계속 탐색합니다.

---

✅ 이런 식으로 DFS는:

• 각 문자를 하나씩 보면서 선택과 비선택을 모두 탐색합니다.
• 조건(길이4, 모음≥1, 자음≥2)을 만족하면 출력합니다.
• 조건을 만족하거나, 더 진행할 수 없는 지점에 도달하면 이전 단계로 되돌아갑니다.(백트래킹)

---

📌 위 과정을 반복하면

아까 처음의 예시에서 최종적으로 출력되는 암호는 다음과 같은 형태로 모두 찾아집니다.

atci
atcs
atcw
atis
atiw
atsw
acis
aciw
acsw
aisw
tcis
tciw
tcsw
tisw
cisw

이렇게 모든 암호를 DFS + 선택/비선택 + 백트래킹 과정으로 정확하게 찾을 수 있습니다.

---

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

char arr[16];
int check[16] = {0}; // 0: 미선택, 1: 선택
int L, C;
int cnt_mo = 0; // 모음 개수
int cnt_za = 0; // 자음 개수

// 문자가 모음인지 판별하는 함수
bool check_mo(const char ch)
{
    if (ch == 'a' || ch == 'e' || ch == 'o' || ch == 'i' || ch == 'u')
        return true;
    else
        return false;
}

// DFS 재귀 함수
void DFS(int index)
{
    // 기저 조건: 모든 문자를 확인한 경우 (index가 C에 도달)
    if (index == C)
    {
        // 현재까지 뽑은 문자의 개수가 L이고, 모음/자음 조건을 만족하는지 확인
        if ((cnt_mo + cnt_za) == L && cnt_mo >= 1 && cnt_za >= 2)
        {
            // 조건을 만족하면 선택된 문자들을 출력
            for (int i = 0; i < C; i++)
            {
                if (check[i] == 1) // 선택된 문자만 출력
                    cout << arr[i];
            }
            cout << endl; // 줄바꿈
        }
        return; // 재귀 종료
    }
    else
    {
        // 1. 현재 문자를 '선택'하는 경우
        check[index] = 1; // 현재 인덱스의 문자를 선택 표시
        if (check_mo(arr[index])) // 모음이면 모음 개수 증가
            cnt_mo++;
        else // 자음이면 자음 개수 증가
            cnt_za++;

        DFS(index + 1); // 다음 문자로 재귀 호출

        // 백트래킹: 현재 문자의 선택을 '해제' (이전 상태로 복원)
        check[index] = 0;
        if (check_mo(arr[index])) // 모음이면 모음 개수 감소
            cnt_mo--;
        else // 자음이면 자음 개수 감소
            cnt_za--;

        // 2. 현재 문자를 '선택하지 않는' 경우
        DFS(index + 1); // 다음 문자로 재귀 호출
    }
}

int main(void)
{
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> L >> C; // L: 암호 길이, C: 전체 문자 개수

    for (int i = 0; i < C; i++)
        cin >> arr[i];

    // 암호가 사전 순으로 정렬되어야 하므로, 입력 문자들을 미리 정렬
    sort(arr, arr + C);

    DFS(0); // DFS 탐색 시작 (첫 번째 문자부터)

    return 0;
}

개별 코드 설명
1. 전역 변수 및 배열 선언
char arr[16];
int check[16] = {0};
int L, C, cnt_mo = 0, cnt_za = 0;

    
`arr` : 입력된 문자들을 저장하는 배열입니다.
    
`check` : 각 문자를 현재 암호 조합에 **선택했는지 여부**를 저장하는 배열입니다 (1: 선택, 0: 미선택).
    
`L` : 만들 암호의 길이를 나타냅니다.
    
`C` : 입력으로 주어진 전체 문자 개수를 나타냅니다.
    
`cnt_mo` / `cnt_za` : 현재까지 선택된 문자들 중 모음과 자음의 개수를 각각 추적합니다.


2. 모음 판별 함수
bool check_mo(const char ch)
{
    if (ch == 'a' || ch == 'e' || ch == 'o' || ch == 'i' || ch == 'u')
        return true;
    else
        return false;
}

    
주어진 문자 `ch`가 모음(`a`, `e`, `i`, `o`, `u`)인지 여부를 판별하여 `true` 또는 `false`를 반환합니다.


3. DFS 재귀 함수
void DFS(int index)
{
    if (index == C)
    {
        if ((cnt_mo + cnt_za) == L && cnt_mo >= 1 && cnt_za >= 2)
        {
            for (int i = 0; i < C; i++)
            {
                if (check[i] == 1)
                    cout << arr[i];
            }
            cout << endl;
        }
        return;
    }


    
**기저 조건 (`index == C`)**: `index`가 `C`와 같아지면, 이는 모든 `C`개의 입력 문자에 대해 선택/비선택 결정을 완료했음을 의미합니다.
        

            
이 시점에서 현재까지 `check` 배열에 1로 표시된 문자의 개수(`cnt_mo + cnt_za`)가 `L`과 같고, 모음의 개수(`cnt_mo`)가 1개 이상, 자음의 개수(`cnt_za`)가 2개 이상인지 확인합니다.
            
이 모든 조건을 만족하면, `check` 배열을 순회하며 선택된 문자들(`check[i] == 1`)을 사전 순으로 출력하고 줄 바꿈합니다.
            
이후 `return`하여 현재 재귀 호출을 종료하고 이전 단계로 돌아갑니다(백트래킹).
        
    


4. 선택 / 비선택 분기
    else
    {
        // 1. 현재 문자를 '선택'하는 경우
        check[index] = 1;
        if (check_mo(arr[index]))
            cnt_mo++;
        else
            cnt_za++;
        DFS(index + 1);

        // 백트래킹: 현재 문자의 선택을 '해제' (이전 상태로 복원)
        check[index] = 0;
        if (check_mo(arr[index]))
            cnt_mo--;
        else
            cnt_za--;

        // 2. 현재 문자를 '선택하지 않는' 경우
        DFS(index + 1);
    }
}

    
`else` 블록은 `index`가 `C`에 도달하지 않았을 때(아직 결정할 문자가 남아있을 때) 실행됩니다.
    
**현재 문자 `arr[index]`를 `선택`하는 경우:**
        

            
`check[index]`를 `1`로 설정하여 현재 문자를 선택했음을 표시합니다.
            
`check_mo` 함수를 사용하여 `arr[index]`가 모음인지 자음인지 판별하고, 해당 카운터(`cnt_mo` 또는 `cnt_za`)를 1 증가시킵니다.
            
`DFS(index + 1)`을 호출하여 다음 문자에 대한 선택/비선택 결정을 진행합니다.
            
재귀 호출이 끝나고 이 지점으로 돌아오면, **백트래킹**을 수행합니다. 즉, `check[index]`를 다시 `0`으로 설정하고 해당 카운터(`cnt_mo` 또는 `cnt_za`)를 1 감소시켜 현재 문자를 선택하지 않은 상태로 되돌립니다. 이는 다른 경우의 수를 탐색하기 위함입니다.
        
    
    
**현재 문자 `arr[index]`를 `선택하지 않는` 경우:**
        

            
백트래킹 이후, `DFS(index + 1)`을 다시 호출하여 현재 문자를 선택하지 않은 상태에서 다음 문자로 넘어가는 경우를 탐색합니다.
        
    


5. 메인 함수
int main(void)
{
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> L >> C;
    for (int i = 0; i < C; i++)
        cin >> arr[i];

    // 암호가 사전 순으로 정렬되어야 하므로, 입력 문자들을 미리 정렬
    sort(arr, arr + C);

    DFS(0); // DFS 탐색 시작 (첫 번째 문자부터)

    return 0;
}

    
`main` 함수에서는 먼저 표준 입출력 동기화를 해제하여 입출력 속도를 향상시킵니다.
    
`L`과 `C` 값을 입력받습니다.
    
`C`개의 문자들을 입력받아 `arr` 배열에 저장합니다.
    
문제 조건 중 "알파벳은 사전 순으로 정렬되어 있어야 한다"는 요구사항을 만족하기 위해 `std::sort()` 함수를 사용하여 `arr` 배열의 문자들을 **사전 순으로 미리 정렬**합니다. 이 과정을 통해 DFS가 진행되면서 자연스럽게 사전 순으로 암호가 생성되고 출력됩니다.
    
`DFS(0)`을 호출하여 첫 번째 문자(`index` 0)부터 재귀 탐색을 시작합니다.
    
모든 과정이 완료되면 `0`을 반환하며 프로그램을 종료합니다.


결론

    
이 문제는 전형적인 **조합 (Combination)** 문제로, 순서보다는 어떤 문자를 선택하느냐가 핵심입니다.
    
**DFS (깊이 우선 탐색)**를 이용하여 각 문자를 선택하거나 선택하지 않는 방식으로 모든 가능한 경우의 수를 탐색합니다.
    
생성된 암호는 길이가 `L`이어야 하고, 반드시 **모음은 최소 1개, 자음은 최소 2개**를 포함해야 합니다.
    
암호가 **사전 순으로 출력**되도록 하기 위해, 입력된 문자들을 `DFS` 실행 전에 미리 정렬하는 것이 중요합니다.