[백준 알고리즘][백트래킹] 1759번 암호 만들기

문제

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

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

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

입력

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

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

풀이

일단 예제 입력을 보면 알파벳들이 정렬되어 들어오지 않는다. 만든 알파벳도 오름차순이 되게하려면 처음 입력이 들어왔을 때 노드순회를 시작하기 전에 먼저 sort를 해두는 게 좋을 것 같다. 

서로 다른 L개의 알파벳을 만들기 위해서 C가지의 알파벳에서 골라서 사용해야하는데 L보다 C가 더 크거나 같으므로 C개에서 L개를 조합해서 만들어야한다.(하나의 문자를 여러번 쓸 일이 없다) 앞에 문제풀 때처럼 트리를 그리면서 이 알파벳을 사용할지 안할지에 따라서 쭈욱 leaf node로 내려오면 될 것 같다. 마지막 노드가 되었을 때 그 때 포함하고 있는 알파벳의 수가 L이 되면 출력을 해야한다. 부분집합의 합을 구할 때 sum이라는 변수에 계속해서 더할경우 안 더할경우에 맞춰서 더하고 뺐던 것처럼 알파벳을 저장할 수 있는 배열에 해당하는 알파벳을 넣을지 안넣을지를 저장해서, 마지막 node가 되었을 때 그 수가 L과 일치하면 출력하도록 한다. 

코드를 짜다가 모르고 고려안한 조건이 떠올랐다. 알파벳은 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어있어야한다. 

첫번째 버전의 코드에서는 조건을 윗줄의 조건을 고려안해서 파라매터에 현재 어떤 input을 넣을지를 나타내는 int형 current만 있었다. 위의 조건을 해결해주기 위해서 추가로 자음을 셀 수 있는 consonant와 모음을 세는 vowel 변수를 선언했다. 재귀함수를 호출할 때 현재 알파벳을 추가하지 않는다면 current+1, consonant, vowel 로 함수를 호출하고, 만약 현재 모음인 알파벳을 암호에 추가하면 current+1, consonant, vowel+1 로 함수를 호출하고, 현재 자음인 알파벳을 추가할 경우 current+1, consonant+1, vowel로 함수를 호출하게 하였다. length가 L이 되었을 때 암호가 완성되는 것인지 L-1이 되었을 때 완전되는것인지 헷갈려서 여러번 고친 것 같다.

어제 풀었던 백트래킹 암호합을 구할때는 해당 변수를 더하지 않는 경우를 먼저 시도하고 그다음 더하는 경우를 함수호출하도록 했었는데, 이번 문제에서는 출력이 오름차순으로 나와야하기때문에 변수를 오름차순으로 정렬해두고 앞에 있는 변수들을 암호에 추가하는 경우를 먼저 시도하도록 했다!

코드

void backTrack(int current, int consonant, int vowel)

{ //현재 어느알파벳까지왔는지, 자음이 몇개인지, 모음이 몇개인지

int i;

if(length > L+1 || current > C) return ; //길이가 넘어가면 더이상 볼 필요 없음

if(length == L && consonant >= 2 && vowel >= 1 ){

for(i=0; i<L; i++)

printf("%c", currentWord[i]);

printf("\n");

return ; 

}

currentWord[length] = input[current];

length++; 

if(isVowel[current] == 0){

backTrack(current+1, consonant+1, vowel); //현재 알파벳넣고하기

}

else{

backTrack(current+1, consonant, vowel+1); //현재 알파벳넣고하기

}

length--; 

backTrack(current+1, consonant, vowel); //현재알파벳안넣고하기

}