1795

이 문제는 딱 보면 어떻게 해결해야 할지 감이 안잡히는데

그래프를 사용하라 하면 어느정도 문제푸는 방법을 깨닫는다

이 문제에서 힌트는 암호들이 정렬되어 있다는 것이다.

사용하는 문자들의 알파벳 정렬을 그래프의 간선으로 설정해서 표현하고

DFS를 통해서 풀면 된다.

기존 DFS랑 다른 점은 한 번 방문한 점을 또 방문 할 수 있다는 점인데

그 노드에서 빠져 나올 때 방문하지 않은 걸로 바꾸면 풀 수 있다.

#include<iostream> #include<vector> #include<algorithm> #include<cstdio> using namespace std; int map[26][26]; vector<char> v; int L, C; bool test(char t){ if(t == 'a' || t=='e' || t=='i' || t=='o' || t=='u') return true; else return false; } void make_password(int start) { bool visited[26]; visited[start] = true; int jaeum=0; int moeum=0; vector<char> cur; cur.push_back(v[start]); if(test(v[start])) moeum++; else jaeum; int piv=start+1;; while(1) { if(cur.size()==L) { //경우에 있는 경우 if(jaeum>=2 && moeum >=1) { for(int i=0; i<cur.size(); i++) printf("%c", cur[i]); printf("\n"); } if(test(cur[L-1])) moeum--; else jaeum--; visited[cur[L-1]-'a']=false; piv=(int)cur[L-1]-'a'+1; cur.pop_back(); } for(;piv<26;piv++) { if(map[cur[cur.size()-1]-'a'][piv]==1) { char t = 'a'+piv; visited[t-'a']=true; cur.push_back(t); if(test(t)) moeum++; else jaeum++; break; } } if(piv >= 26) { //여기서 더이상 찾을 수 없는 경우 if(test(cur[cur.size()-1])) moeum--; else jaeum--; visited[cur[cur.size()-1]-'a']=false; piv = (int)cur[cur.size()-1]-'a'+1; cur.pop_back(); } if(cur.size()==0) break; } } int main() { char tmp; scanf("%d %d", &L, &C); for(int i=0; i<C; i++) { cin>>tmp; v.push_back(tmp); } sort(v.begin(), v.end()); for(int i=0; i<v.size()-1; i++) for(int j=i+1; j<v.size(); j++) map[v[i]-'a'][v[j]-'a']=1; for(int i=0; i<=v.size()-L; i++) make_password(i); return 0; }