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

문제링크

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

1759번: 암호 만들기

 

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다.
또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다.
즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15)
다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다.
주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

 

문제정리

1. 암호는 최소 한개의 모음과 최소 두 개의 자음으로 구성되어있습니다.
2. 암호는 알파벳의 오름차순으로 나타내야합니다.
3. C개의 문자들이 모두 주어지면 가능성있는 암호를 모두 출력해야합니다.

이번 문제의 경우 이 바로전에 풀었던 문제랑 비슷한데 조건이 하나 추가되었습니다.

https://bokhead.tistory.com/113

[백준 - C#] 6603번 로또

6603번 문제와 같이 1759번 암호만들기 문제도 DFS 전체탐색으로 풀되 백트래킹을 이용하여 불필요한 탐색은 하지 않는 방식으로 문제 풀이를 진행하였습니다.

하지만 출력 전에 모음이 1개 이상인지 자음은 2개 이상인지 검사하여 출력을 할지 안할지 결정하는 코드가 추가 되었습니다.

 

이번에도 백트래킹과 DFS 문제를 푸는 좋은 기회가 되었습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int L = int.Parse(input[0]);
    int C = int.Parse(input[1]);
 
    string[] arr = reader.ReadLine().Split();
    Array.Sort(arr);
 
    char[] screct = new char[L];
 
    DFS(0, 0);
 
    writer.Close();
    reader.Close();
 
    void DFS(int start, int count)
    {
        if (count == L) // 암호 L개가 채워졌을 때
        {
            int vowel = 0;
            for (int i = 0; i < L; i++)
            {
                // 모음 체크
                if (screct[i] == 'a' || screct[i] == 'e' || screct[i] == 'i'
                    || screct[i] == 'o' || screct[i] == 'u')
                {
                    vowel++;
                }
            }
 
            // 모음은 1개 이상 자금은 2개이상 검사
            if (vowel >= 1 && L - vowel >= 2)
            {
                for (int i = 0; i < L; i++)
                {
                    writer.Write($"{screct[i]}");
                }
                writer.WriteLine();
            }
 
            return;
        }
 
        for (int i = start; i < C; i++) // 입력 받은 암호를 전부 탐색
        {
            screct[count] = char.Parse(arr[i]);
            DFS(i + 1, count + 1); // 다음 암호를 입력하는 재귀함수
        }
    }
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.