[백준] 1759 암호 만들기(C++)

 

문제 URL:

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

1759번: 암호 만들기

 

이 문제는 C개의 문자들이 주어졌을 때, 가능성 있는 암호들을 모두 구하는 문제로 브루트포스 알고리즘과 백트래킹을 이용하는 문제이다. 

 

문제 자체는 어렵지 않았지만 아직 백트래킹 문제에 익숙하지 않아서 다른 사람의 풀이를 찾아보았다. 

먼저, 주어진 문자들을 오름차순으로 정렬한 뒤 반복문을 통해 모든 알파벳을 검사하며 조건에 맞는 문자열을 출력하였다.

select() 함수에서는 브루트포스 알고리즘을 통해 암호 길이에 맞는 문자를 선택하였고, check() 함수에서는 선택한 문자들이 조건에 맞는지 검사하였다. 

---

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

int lock_size, letter_size;
char letter[16];
int visit[16];

void check() {  // 암호 구성 체크(모음, 자음)
	char str[16];
	int vowel = 0, idx = 0;

	//문자열 검사
	for (int i = 0; i < letter_size; i++) {
		if (visit[i]) {
			str[idx] = letter[i];
			idx++;
			if (letter[i] == 'a' || letter[i] == 'e' || letter[i] == 'i' || letter[i] == 'o' || letter[i] == 'u')
				vowel++;
		}
	}
	str[lock_size] = '\0';

	// 모음이 1개 이상이면서 자음이 2개 이상일 때 출력
	if (vowel && lock_size - vowel >= 2)
		cout << str << '\n';
}

int select(int idx, int cnt) {
	if (cnt == lock_size) {  // 길이가 lock_size가 되면 선택한 문자들 검사
		check();
		return 0;
	}

	if (idx == letter_size) // 마지막 문자를 넘어서는 경우
		return 0;

	// 해당 좌표를 방문할 경우
	visit[idx] = 1;
	select(idx + 1, cnt + 1);

	// 해당 좌표를 방문하지 않을 경우
	visit[idx] = 0;
	select(idx + 1, cnt);

	return 0;
}


int main() {
	cin >> lock_size >> letter_size;

	for (int i = 0; i < letter_size; i++)
		cin >> letter[i];
	
	// 알파벳 정렬
	sort(letter, letter + letter_size);

	// 오름차순으로 모든 알파벳 검사
	for (int i = 0; i <= letter_size - lock_size; i++) {  // select()에서 알파벳을 lock_size만큼 선택하기 때문에 letter_size - lock_size까지만
		memset(visit, 0, sizeof(visit));
		visit[i] = 1;
		select(i + 1, 1);
	}

	return 0;
}

참고: https://wtg-study.tistory.com/79