백준 16719번 ZOAC로 풀어보는 Brute force DFS 알고리즘

백준 16719번 문제가 만족하기 위해서는

 

문자열에 문자가 하나씩 추가될때,  최대한 가장 빠른문자가 나오고

그 다음 나오는 문자는 선행되어 나왔던 문자보다는 분명 느린 문자이므로, 최대한 뒤쪽에 나오는 것이 

사전순으로 유리합니다.

 

이 과정을 brute force 무식하게 푸는 방법.. 순서대로 가능한 수를 나열하며 푸는 방식으로 풉니다.

 

이때 DFS가 활용되는 경우가 많은데 이번 문제에 꽤나 적합했다고 생각합니다.

 

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

bool visit[100];

// 사전순으로 출력
// 조건1. 사전순으로 가장 빠른 문자가 먼저 출력되어야 한다.
// 조건2. 선행된 dfs에서 출력된 문자가 나보다 사전순 빠른 문자이므로
//        선행되어 출력된 문자보다 원문자열에서 index가 뒤에 있는 문자가 출력되어야 사전순으로 더 빠르다.
//        ex)  CAD를 출력한다면, "A" 출력 후  C가 D보다 빠르다하여 "CA"로 하는 것보다 "AD"가 더 앞선 사전순...

// dfs는 for문을 돌며 cur_idx ~ size끝까지, brute하게 dfs로 찾는다.
// 위의 2조건이 만족하게 되면 자신의 바로 뒷부분에 문자를 삽입한후 출력하게 된다.

// 앞쪽에 출력된 문자가 최대한 오래 보존될 수록 좋으므로
// stack과 같은 개념을 사용한다 DFS!!
void dfs(vector<pair<char, int>> &str, string &answer, int cur_idx,int str_idx) {

	for (int i = cur_idx+1; i < str.size(); i++) {
		if (str[cur_idx].second < str[i].second && !visit[i]) {
			visit[i] = true;
			char tmp[2] = { str[i].first,NULL};	// string의 함수들은 문자열대상이므로 문자를 문자열로 변환.
			answer.insert(str_idx+1,tmp);
			cout << answer << "\n";
			dfs(str, answer,i,str_idx+1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	vector<pair<char,int>> str;
	string answer;
	char temp;

	// 더미 데이터,
	// dfs에서 back(stack의 pop)하며 원문자열보다 앞부분 문자를 채워나가는데.
	// 더미가 없다면 가장 먼저 출력된 문자의 앞부분은 출력할 수 없게 되버린다.
	str.push_back({ 't',0});

	//한문자씩 받아 str vector에 넣어준다.
	// pair는 {문자,원문자열에서의 index + 1 (더미데이터로 인해 +1) };
	while ((temp = cin.get()) != '\n') {
		str.push_back({ temp,str.size()});
	}

	//문자를 사전순으로 sort
	sort(str.begin()+1, str.end());

	dfs(str, answer, 0, -1);
}