백준 [C언어] 1759 : 암호 만들기

✅ 문제

1. 사전 순 정렬 

2. 모음이 1개 이상

3. 자음이 2개 이상

 

✅ 해결 과정

1. 알파벳 C개 입력 받고 quick sort 사용해서 사전 순 정렬

2.  dfs(깊이 우선 탐색)을 이용해 모든 가능한 경우의 수를 구한다.

3. L길이의 암호가 만들어지면 자음과 모음의 개수를 카운트하여 자음이 2개 이상, 모음이 1개 이상일 때만 출력해준다.

 

 ✅ DFS

https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

 

✅ 코드

#include <stdio.h>
#include <stdlib.h>

int L, C;
char alphabet[16];  //사용했을 법한 문자
char password[16];  //가능한 암호
int selected[16];  //선택 여부 확인

//퀵소트 비교함수 (오름차순)
int cmp(const void* a, const void* b) {
	if (*(char*)a > *(char*)b) return 1;
	else return -1;
}

//모든 경우의 수에 대한 암호 만들어 보기 (depth : 암호 길이, start : 가능한 알파벳 시작점)
void dfs(int depth, int start) {
    
    //암호 다 완성되면 모음, 자음 개수 검사
	if (depth == L) {
		int vowel = 0;         //모음 개수
		int consonant = 0;    //자음 개수
		for (int i = 0; i < depth; i++) {
			if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u') {
				vowel++;
			}
			else
				consonant++;
		}
        //모음1이상, 자음2이상이면 출력하고 끝내기
		if (vowel && consonant >=2) {
			for (int i = 0; i < depth; i++)
				printf("%c", password[i]);
			printf("\n");
			return;
		}
		else
			return;
	}
    
    //C개의 가능한 알파벳에 대해
	for (int i = start; i < C; i++) {
		if (!selected[i]) {    //아직 선택되지 않은 알파벳이면
			selected[i] = 1;        //선택 표시하고
			password[depth] = alphabet[i];   //알파벳 추가
			dfs(depth + 1, i + 1);        //선택된 알파벳은 제외하고 계속 진행
			selected[i] = 0;        
		}
	}
}

int main() {
	scanf("%d %d", &L, &C);
	for (int i = 0; i < C; i++)
		scanf(" %c", &alphabet[i]);
	qsort(alphabet, C, sizeof(char), cmp);
    
	dfs(0, 0);

	return 0;
}