WORDCHAIN 알고리즘 문제해결 전략 코드에 오류가 있는 것 같습니다.

  • leechhe90
    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
    fleo0917

    ak ka ab bc 왜 안 되죠?


    9년 전 link
  • leechhe90
    leechhe90

    아 제가 문제 이해를 잘못했었네요
    죄송합니다 ㅠㅠ


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.