개요

백준 1759: 암호만들기

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

• 출력
  각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근 방식

1. 기본적으로 모든 암호를 다 봐야하니 백트래킹방식을 통해서 접근을 했다.

2. 재귀함수인 Backtracking에 현재 인덱스, 현재 인덱스에서 자음 갯수,
   모음 갯수를 매개변수로 사용하여 각 단계에서의 자음과 모음을 체크해줬다.

void Backtracking(int cur, int consonant, int vowel) {

3. 전체적인 흐름은
   index가 끝에 다다르면 return

   if (cur == C) return;

   현재 문자 담는 벡터의size가 L-1이라면 자음 모음 갯수 체크해서 출력하기

   if (Ans.size() == L - 1) {
   		//cur인덱스의 글자가 모음이라면
   		if (Letters[cur] == 'a' || Letters[cur] == 'e' || Letters[cur] == 'i' || Letters[cur] == 'o' || Letters[cur] == 'u') {
   			// 지금까지 자음이 2개 이상이여야함
   			if (consonant >= 2) {
   			string tmp = "";
   			//char문자들 합쳐준 후
   			for (auto iter = Ans.begin(); iter != Ans.end(); ++iter) {
   				tmp += *iter;
   			}
   			//cur인덱스에 해당하는 문자까지 추가해서 답벡터에 넣어줌
   			printAns.push_back(tmp + Letters[cur]);
   			}
   
   		}
   		//cur인덱스의 글자가 자음이라면 지금까지 자음,모음이 1개이상씩 있어야함
   		else if (consonant >= 1 && vowel >= 1) {
   				string tmp = "";
   				for (auto iter = Ans.begin(); iter != Ans.end(); ++iter) {
   					tmp += *iter;
   				}
   				//cur인덱스에 해당하는 문자까지 추가해서 답벡터에 넣어줌
   				printAns.push_back(tmp + Letters[cur]);
   		}
   		//위의 조건에 해당 안되면 패스
   	}

   현재 인덱스의 문자를 포함 안하고 재귀,

   //cur인덱스의 문자 패스하고 dfs
   	Backtracking(cur + 1, consonant, vowel);
   

   현재 인덱스를 포함한다면 자음인지 모음인지 체크해서 재귀,

   	//cur인덱스의 문자 패스하고 dfs
   	Backtracking(cur + 1, consonant, vowel);
   
   	//cur인덱스의 문자 포함해주고 
   	Ans.push_back(Letters[cur]);
   	if (Letters[cur] == 'a' || Letters[cur] == 'e' || Letters[cur] == 'i' || Letters[cur] == 'o' || Letters[cur] == 'u')
   		//만약 문자가 모음이면 vowel+1해주고 dfs
   		Backtracking(cur + 1, consonant, vowel + 1);
   	else {
   		//자음이면 consonant+1
   		Backtracking(cur + 1, consonant + 1, vowel);
   	}

   재귀가 끝나고 돌아왔을 때 마지막에 push해준값 pop해주면서 해당 값 다시 방문할 수 잇도록 체크

   //매번 dfs가 끝나고 돌아오면 다시 이노드를 방문할 수 있으므로 해당 cur인덱스의 문자를 제거해준다. 
   Ans.pop_back();

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int L = 0, C = 0;
char Letters[16];
//각 dfs에서 사용할 char문자 담는 벡터
vector<char>Ans;
//4글자짜리가 나온다면 저장해서 마지막에 sort하는 벡터
vector<string>printAns;

void Input() {
	cin >> L >> C;
	for (int i = 0; i < C; i++) {
		cin >> Letters[i];
	}
	//알파벳순으로 정렬
	sort(Letters, Letters + C);
}
/// <summary> 
/// Index를 parameter로 받아와서 Ans 길이가 답 배열과 같으면 Ans출력
/// 해당 index값을 안더해준것과 더해준 것으로 재귀를 나눠서 진행
/// 끝나고 Ans에서 해당 값을 빼줌으로서 노드 방문 초기화
/// </summary>
/// <param name="Index(cur)"></param>
void Backtracking(int cur, int consonant, int vowel) {
	//index가 끝에 다다르면 return한다.
	if (cur == C) return;
	//Ans.size가 L일때 출력하면 안되는 게, 만약 cur이 c-1일때 마지막값을 푸시하고 DFS(cur+1)을 실행하면
	// cur+1은 c이므로 return 당해서 출력 하는 부분이 호출이 안됨.
	if (Ans.size() == L - 1) {
		//cur인덱스의 글자가 모음이라면
		if (Letters[cur] == 'a' || Letters[cur] == 'e' || Letters[cur] == 'i' || Letters[cur] == 'o' || Letters[cur] == 'u') {
			// 지금까지 자음이 2개 이상이여야함
			if (consonant >= 2) {
			string tmp = "";
			//char문자들 합쳐준 후
			for (auto iter = Ans.begin(); iter != Ans.end(); ++iter) {
				tmp += *iter;
			}
			//cur인덱스에 해당하는 문자까지 추가해서 답벡터에 넣어줌
			printAns.push_back(tmp + Letters[cur]);
			}

		}
		//cur인덱스의 글자가 자음이라면 지금까지 자음,모음이 1개이상씩 있어야함
		else if (consonant >= 1 && vowel >= 1) {
				string tmp = "";
				for (auto iter = Ans.begin(); iter != Ans.end(); ++iter) {
					tmp += *iter;
				}
				//cur인덱스에 해당하는 문자까지 추가해서 답벡터에 넣어줌
				printAns.push_back(tmp + Letters[cur]);
		}
		//위의 조건에 해당 안되면 패스
	}

	//cur인덱스의 문자 패스하고 dfs
	Backtracking(cur + 1, consonant, vowel);

	//cur인덱스의 문자 포함해주고 
	Ans.push_back(Letters[cur]);
	if (Letters[cur] == 'a' || Letters[cur] == 'e' || Letters[cur] == 'i' || Letters[cur] == 'o' || Letters[cur] == 'u')
		//만약 문자가 모음이면 vowel+1해주고 dfs
		Backtracking(cur + 1, consonant, vowel + 1);
	else {
		//자음이면 consonant+1
		Backtracking(cur + 1, consonant + 1, vowel);
	}
	//매번 dfs가 끝나고 돌아오면 다시 이노드를 방문할 수 있으므로 해당 cur인덱스의 문자를 제거해준다. 
	Ans.pop_back();
}

void Solution() {
	Backtracking(0, 0, 0);
	sort(printAns.begin(), printAns.end());
	for (auto iter = printAns.begin(); iter != printAns.end(); ++iter) {
		cout << *iter << '\n';
	}
}

int main() {
	Input();
	Solution();
}

문풀후생

백트래킹 문제를 푼지 얼마 안 되었지만 DFS로 푸는 방식과 비슷한거 같다.
백트래킹에서 재귀함수로 구현한 방식이
dfs에서 방문배열을 체크하여 연결된 노드로 진행한 다음 다시 해당 노드로 돌아올때,
방문배열을 false로 바꿔줘 해당 노드를 다시 탐색이 가능하게
만드는 것과 똑같다.

처음엔 마지막에 해당 노드값 지우는 부분을 vector의 iterator을 사용하여
해당 값이면 erase함수로 지웠다.
문제는 해당 값이 마지막 값이라 erase로 지우고 다음값을 반환하면
end값인데 해당 iter에서 더 증가해버려서 오류가 났다.

for(auto iter=Ans.begin();iter!=Ans.end();++iter)
{
	if(*iter==Letters[cur])
    	iter=Ans.erase(iter);
        //그냥 break하던지 iter을 여기선 증가 안시키면 된다. 
}

나중에 생각해보니 어차피 dfs처럼 제일 깊은 노드로 갔다가 return하는 구조라
저렇게 번거롭게 안하고

Ans.pop_back()

하면 된다..

또한 출력할 때 처음엔 Ans.size()가 L일때 출력하게끔 했더니
예제 여러개가 누락되었다.
이유를 생각해보니 L일때 출력하게 되면
현재 cur값이 마지막 값일때, 현재 값을 Ans에 push_back()해준 후
바로 backtracking(cur+1)을 하게되고 거기서 return을 해버려서
출력하는 부분이 호출이 안된다.
따라서 사이즈가 L-1일 때 현재값을 조사해서 넣어주고 출력을 미리해야한다.