영벨롭 개발 일지

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

알고리즘 문제 풀이/BOJ

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

영벨롭 2022. 4. 6. 16:15

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

 

1759번: 암호 만들기

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

www.acmicpc.net

 

 이 문제는 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;
}
반응형