WORDCHAIN 알고리즘 문제해결 전략 코드에 오류가 있는 것 같습니다. leechhe90 알고리즘 문제 해결전략의 코드에 문제가 있는 것 같습니다.제가 갖고 있는 책은 3쇄인데, 오일러 트레일로 접근했을 시 새로 만든 연결을 처리하는 과정이 문제인 것 같습니다. 4 ab bc ak ka 를 넣었을 때 IMPOSSIBLE이 출력되어야 하는데 가능한 것으로 출력하는데 케이스를 더 추가해야할 것 같습니다. 아래는 제가 작성한 코드인데, 마지막 정답을 출력하는 곳에 주석부분이 필요하다고 생각합니다. 혹시 제가 문제 이해를 잘못한 걸까요? 답변해주시면 감사하겠습니다 :) #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <utility> #include <string> using namespace std; vector<int> ret; vector<vector<int>> adj; vector<int> indegree; vector<int> outdegree; void getEulerCircuit(int cur){ for( int next = 0 ; next < 26 ; ++next){ while( adj[cur][next] ){ adj[cur][next]--; getEulerCircuit(next); } } ret.push_back(cur); } int main(){ int c; scanf("%d",&c); while(c--){ ret.clear(); adj = vector<vector<int>>(26,vector<int>(26)); outdegree = vector<int>(26); indegree = vector<int>(26); vector<string> words[26][26]; int n; scanf("%d",&n); for( int i = 0 ; i < n ; ++i ){ string word; cin >> word; adj[word[0]-'a'][word[word.length()-1]-'a']++; words[word[0]-'a'][word[word.length()-1]-'a'].push_back(word); outdegree[word[0]-'a']++; indegree[word[word.length()-1]-'a']++; } bool possible = true; int plus1 = 0; int minus1 = 0; for( int i = 0 ; i < 26 ; ++i ){ int delta = outdegree[i]-indegree[i]; if( delta > 1 || delta < -1 ){ possible = false; break; } if ( delta == 1 ) ++plus1; else if( delta == -1 ) ++minus1; } if( possible ) possible = (plus1 == 1 && minus1 == 1 ) || (plus1 == 0 && minus1 == 0 ); if( !possible ){ printf("IMPOSSIBLE\n"); continue; } for( int i = 0 ; i < 26 ; ++i ){ if( outdegree[i] == indegree[i]+1 ){ int start = i; // int dest; // for( int j = 0 ; j < 26 ; ++j ){ // if(indegree[i] == outdegree[i]+1){ // dest = i; // break; // } // } // adj[dest][start] = true; getEulerCircuit(start); break; } } if( ret.empty() ){ for( int i = 0 ; i < 26 ; ++i ){ if(outdegree[i]){ getEulerCircuit(i); break; } } } if( ret.size() != n+1 ) printf("IMPOSSIBLE\n"); else{ reverse(ret.begin(), ret.end()); string ans; for( int i = 1 ; i < ret.size() ; ++i ){ if( ans.size() ) ans += " "; // if( words[ret[i-1]][ret[i]].empty() ){ // ans = "IMPOSSIBLE"; // break; // } ans += words[ret[i-1]][ret[i]].back(); words[ret[i-1]][ret[i]].pop_back(); } printf("%s\n", ans.c_str()); } } return 0; } 9년 전
2개의 댓글이 있습니다. fleo0917 ak ka ab bc 왜 안 되죠? 9년 전 link leechhe90 아 제가 문제 이해를 잘못했었네요 죄송합니다 ㅠㅠ 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
leechhe90
알고리즘 문제 해결전략의 코드에 문제가 있는 것 같습니다.제가 갖고 있는 책은 3쇄인데,
오일러 트레일로 접근했을 시 새로 만든 연결을 처리하는 과정이 문제인 것 같습니다.
4
ab bc ak ka
를 넣었을 때 IMPOSSIBLE이 출력되어야 하는데 가능한 것으로 출력하는데 케이스를 더 추가해야할 것 같습니다.
아래는 제가 작성한 코드인데, 마지막 정답을 출력하는 곳에 주석부분이 필요하다고 생각합니다.
혹시 제가 문제 이해를 잘못한 걸까요?
답변해주시면 감사하겠습니다 :)
9년 전