DICTIONARY

DICTIONARY

다시 풀어본 문제, 좀 고민했지만 위상정렬 문제.

옛날 풀이가 위상정렬을 공부하고 풀었기 때문에 더 깔끔하게 푼 것 같다. 

아무튼 위상 정렬에는 DFS 로 푸는 방법과 BFS로 푸는 방법이 있는데, 나는 이제 BFS로 익숙해져있다.

C언어로도 한번 바꿔봐야 겠다.

<정답 코드>

include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
int tc, n;
vector<vector<int>> order(26);
bool used[26];
int indegree[26];
string word[1000];
void init()
{
    for (int i = 0; i < 26; i++) {
        used[i] = false;
        indegree[i] = 0;
        order[i].clear();
    }
 
}
void compare(int n1, int n2)
{
    int len = word[n1].size() > word[n2].size() ? word[n2].size() : word[n1].size();
    char tmp1, tmp2;
    for (int i = 0; i < len; i++) {
        //단어 비교해서 그래프로 엮어주기.
        if (word[n1][i] != word[n2][i]) {
            tmp1 = word[n1][i];
            tmp2 = word[n2][i];
 
            order[tmp1 - 'a'].push_back(tmp2 - 'a');
            indegree[tmp2 - 'a']++;
 
            used[tmp1 - 'a'] = true;
            used[tmp2 - 'a'] = true;
 
            break;
        }
    }
 
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
 
        init();
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> word[i];
        }
 
        //단어 하나씩 비교해보는 함수
        for (int i = 1; i < n; i++) {
            compare(i - 1, i);
        }
 
        int start = -1;
 
 
        //DAG라면 출발점이 존재할 것이므로 탐색
        for (int i = 0; i < 26; i++) {
            if (indegree[i] == 0 && used[i])
            {
                start = i; break;
            }
        }
 
        //DAG가 아니라서 출발점이 존재하지 않을 때
        if (start == -1)
            cout << "INVALID HYPOTHESIS";
        else {
 
 
            //BFS, indegree 값을 이용해서 위상정렬, 정렬된 값은 ans 에 push
            queue<int> q;
            queue<int> ans;
            q.push(start);
 
            while (!q.empty())
            {
                int now = q.front();
                ans.push(now);
                q.pop();
 
                for (int i = 0; i < order[now].size(); i++) {
                    int next = order[now][i];
                    indegree[next]--;
                    if (indegree[next] == 0)
                    {
                        q.push(next);
                    }
 
                }
            }
 
            //시작점이 아닌 곳에서 DAG 조건이 성립하지 않을 때 탐색
 
            for (int i = 0; i < 26; i++) {
                if (used[i] && indegree[i] != 0)
                    start = -1;
            }
 
 
 
            if (start == -1) {
                cout << "INVALID HYPOTHESIS";
            }
 
            //정답이 있는 경우 정답 출력.
            else {
 
                int size = ans.size();
                for (int i = 0; i < size; i++)
                {
                    cout << char(ans.front() + 'a');
                    ans.pop();
                }
 
                for (int i = 0; i < 26; i++) {
                    if (!used[i])
                        cout << char(i + 'a');
                }
            }
        }
 
        cout << endl;
    }
 
    return 0;
 
}