고대어 사전 문제 질문입니다.

  • best88
    best88

    '프로그래밍 대회에서 배우는 알고리즘 문제해결전략'에서 고대어 사전을 보고 문제를 풀어봤는데...
    책에 있는 소스 그래로 구현해서 돌려봤는데 정답이 다르게 나옵니다.
    고대어 사전 문제 모범 답안을 알고 싶습니다 ㅠㅠ


    3년 전
2개의 댓글이 있습니다.
  • Signin
    Signin
    • 알고스팟에서 다른 사람의 소스 코드는 풀기 전까지 원칙적으로 비공개인 것으로 알고 있습니다.
    • 이런 경우 소스코드를 함께 올려주시면 다른 분들이 알기 쉽습니다.

    3년 전 link
  • best88
    best88

    제출했던 소스입니다ㅠㅠ
    도움 주시면 감사하겠습니다 ㅠㅠ

    vector words;
    vector> adj;
    vector order, rev_order, seen;

    void makegraph()
    {
    adj = vector>(26, vector(26,0));

    for(int j = 1; j < words.size() ; ++j)
    {
        int i = j - 1; int len = min(words[i].size(), words[j].size());
    
        for(int x = 0 ; x < len ; ++x)
        {
            if(words[i][x] != words[j][x])
            {
                int a = words[i][x] - 'a';
                int b = words[j][x] - 'a';
                adj[a][b] = 1; 
                break;
            }
        }
    }

    }
    void dfs(int here)
    {
    seen[here] = 1;

    for(int there = 0 ; there < adj.size() ; there++)
        if(adj[here][there] && !seen[there])
            dfs(there);     
    order.push_back(here);

    }

    vector topologicakSort()
    {
    int n = adj.size();
    seen = vector(n, 0);
    order.clear();

    for(int i = 0 ; i < n ; ++i)
    {
        if(!seen[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    
    for(int i = 0 ; i < n ; ++i)
        for(int j = i + 1 ; j < n ; ++j)
            if(adj[order[j]][order[i]])
                return vector<int>();
    
    return order;

    }

    int main()
    {
    int _case, _word;
    string word;

    cin>>_case;
    for(int i = 0 ; i < _case ; i++)
    {
        cin>>_word; 
        for(int j  = 0 ; j < _word ; j++)
        {
            cin>>word;
            words.push_back(word);
        }
        makegraph();
        vector<int> ref = topologicakSort();
        if(ref.size() == 0)
        {
            cout<<"INVALID HYPOTHESIS"<<endl;           
        }
        else
        {
            for(int x = 0 ; x < ref.size() ; x++)
            {           
                char temp = 'a' + ref[x];
                cout<<temp;
            }
        }
    }   
    return 0;

    }


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