백준 1759

ALGORITHM
2025-09-09

암호 만들기

관련 개념

#백트래킹 #DFS

문제

백준 1759

📌 1 단계 : 문제 분석하기

  • 문제를 읽고, 사용 할 수 있는 방법은 brute force의 방법이다.
  • 하지만 냅다 모든 경우의 수를 계산하면 가능한 경우의 수가 너무 많기에, 적절히 가지치기를 해야 한다.

📌 2 단계 : 손으로 풀어보기

  1. 알파벳을 입력 받는다.
  2. 정렬한다.
  3. 경우의 수를 계산한다.

📌 3 단계 : 슈도 코드 작성하기

  • 생략

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm>
#include <set>
 
using namespace std;
int L, C;
vector<char> characters;
 
void dfs(int depth, int index, int consonant, int vowel, string word) {
 
    // 종료 조건
    if (depth == L && (vowel >= 1 && consonant >= 2)) {
        cout << word << '\n';
        return;
    }
 
		// 이 테크닉이 핵심임 
    for (int i = index; i < C; i++) {
        
        // 해당 단어가 모음인 경우
        if (characters[i] == 'a' || characters[i] == 'e' || characters[i] == 'i' || characters[i] == 'o' || characters[i] == 'u') dfs(depth + 1, i + 1, consonant, vowel + 1, word + characters[i]);
        // 해당 단어가 자음인 경우
        else dfs(depth + 1, i + 1, consonant + 1, vowel, word + characters[i]);
 
    }
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> L >> C;
 
    for (int i = 0; i < C; i++) {
        char input;
        cin >> input;
        characters.push_back(input);
    }
 
    sort(characters.begin(), characters.end());
 
    dfs(0, 0, 0, 0, "");
 
}

📌 5 단계 : 배운점

  • 조합론에 굉장히 약했었는데, 어떻게 접근해야 할지 깨달았다.
  • bfs, dfs의 활용법은 정말 무궁무진하다.
  • 맨처음에 접근했을때는, 1를 택하는 경우, 2개를 택하는 경우, 3개를 택하는 경우를 따지면서 접근하니 이해가 잘 안됐는데, 백 트래킹의 방식으로 생각을 하니 모든 조합의 수를 쉽게 계산 할 수 있었다.
  • 아래 그림은 정답의 풀이는 아니지만, 모든 경우의 수를 계산하는 방법이다.
  • 알고리즘 시간에 배운 종료 조건을 잘 설정하고, 필요 없는 가지는 탐색하지 않는다!!
  • index를 활용하는 것이 핵심