[백준Baekjoon]1759: 암호 만들기/C++

문제

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

풀이

여러 알파벳들을 통해 가능한 모든 암호를 조합해야 한다. 

따라서 백트래킹 알고리즘을 사용하였다. 

 

백트래킹을 사용하면서 생각해야할 점은

1. 지나간 단계에 대한 방문 처리를 해주어야 한다.
2. 탐색이 끝난 후에는 방문 여부를 포함하여 이전 단계로 복원시켜 두어야 한다. 

#include <bits/stdc++.h> 
using namespace std;
#define MAX 15

int L, C;
char arr[MAX];
string S;
bool check, visited[MAX];

void BackTracking(int x) {
	
	if (x == L ) {
		int cnt1 = 0, cnt2 = 0;

		for (int i = 0; i < x; i++) {
			if ((S[i] == 'a' || S[i] == 'e' || S[i] == 'i' || S[i] == 'o' || S[i] == 'u')) {
				cnt1++;
			}
			else {
				cnt2++;
			}
		}

		if (cnt1 >= 1 && cnt2 >= 2) {
			cout << S << '\n';
			return;
		}
	}

	for (int i = 0; i < C; i++) {
		if (!S.empty()) {
			if (S[x - 1] > arr[i])continue;
		}
		if (!visited[i]) {
			visited[i] = true;
			S += arr[i];
			BackTracking(x + 1);
			S.pop_back();
			visited[i] = false;
		}
		
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> L >> C;

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

	BackTracking(0);
}