[백준 BOJ][C++]1759번 암호 만들기 풀이: DFS

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

1759번: 암호 만들기

 

 이 문제는 DFS로 해결할 수 있습니다. 

 

 [풀이 과정]

1. L과 C 입력

2. C개의 알파벳 입력하고 num에 저장

3. num을 오름차순으로 정렬

4. 모든 원소에 대해 순차적으로 dfs 실행

5. 현재 알파벳보다 다음에 위치한 알파벳에 대해 아직 방문 여부 체크

6. 아직 방문하지 않았다면 방문 표시 후, arr[depth]=다음 알파벳, 자음인지 모음인지 체크 후 dfs 호출후 방문 표시 해제

7. depth가 L이고 자음이 2개 이상, 모음이 1개 이상이라면 arr의 모든 원소 출력

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>

using namespace std;

int L, C;
char alphabet[16];
char arr[16];
bool visit[16] = { false, };

bool is_consonant(char c) {
	if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
		return false;
	return true;
}

void dfs(int idx, int c, int v, int depth) {

	if (depth == L && c > 1 && v > 0) {
		for (int i = 0; i < L; i++)
			cout << arr[i];
		cout << endl;
		return;
	}
	else if (depth == L && (c < 2 || v < 1))
		return;

	for (int i = idx + 1; i < C; i++) {
		if (!visit[i]) {
			visit[i] = true;
			char ch = alphabet[i];
			arr[depth] = ch;
			if (is_consonant(ch))
				dfs(i, c + 1, v, depth + 1);
			else
				dfs(i, c, v + 1, depth + 1);
			visit[i] = false;
		}
	}

}

int main(void) {

	cin >> L >> C;

	for (int i = 0; i < C; i++) {
		cin >> alphabet[i];
	}

	sort(alphabet, alphabet + C);

	for (int i = 0; i < C; i++) {
		memset(visit, false, sizeof(visit));
		arr[0] = alphabet[i];
		visit[i] = true;
		int c = 0;
		int v = 0;
		if (is_consonant(alphabet[i])) {
			c++;
		}
		else {
			v++;
		}
		dfs(i, c, v, 1);
	}

	return 0;
}