DICTIONARY

문제 출처 : https://algospot.com/judge/problem/read/DICTIONARY

이 문제에서 얻어 갈 수 포인트는 위상정렬을 한 후 유효성을 검증하는 것이다.

위상정렬은 DAG에서만 그 유효성을 입증 받을 수 있는데, 이 문제의 경우 주어진 그래프가 DAG가 아닐 수도 있다.

처음에 인접행렬방식으로 그래프를 만든다면, 위상정렬을 모두 마친 후 아래와 같은 방법으로 싸이클의 여부를 알아 낼 수 있다.

위상정렬한 결과 i번 노드와 j번 노드가 순서대로 있다면( i -> j ) j번째 노드에서 i번째로 가는 간선이 있다면 DAG가 아닌것이 되는 것이다.

그것을 인접행렬에서 모두 확인해 주면 된다.(인접 리스트라면 간선의 여부를 찾는데 시간이 더 소요될 것이다)

코드는 아래와 같다.

#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector< vector<int> > adj;
vector<bool> visited;
vector<int> order;
 
void dfs(int here) {
    visited[here] = true;
    for (int there = 0; there < adj.size(); there++) {
        if (adj[here][there] && !visited[there]) {
            dfs(there);
        }
    }
    order.push_back(here);
}
 
bool topologicalSort() {
    int n = adj.size();
    visited = vector<bool>(n, false);
    order.clear();
    for (int i = 0; i < n; i++) {
        if (!visited[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 false;
            }
        }
    }
    return true;
}
 
int main() {
    int C;
    scanf("%d ", &C);
    while (C--) {
        int N;
        scanf("%d ",&N);
        vector<string> str;
        adj = vector< vector<int> >(26, vector<int>(26, 0));
        for (int i = 0; i < N; i++) {
            char s[21];
            scanf("%s", s);
            str.emplace_back(s);
        }
        for (int i = 0; i < N - 1; i++) {
            int len_cur = str[i].length();
            int len_next = str[i + 1].length();
            int len = len_cur < len_next ? len_cur : len_next;
            for (int j = 0; j < len; j++) {
                if (str[i][j] != str[i + 1][j]) {
                    adj[str[i][j] - 'a'][str[i + 1][j] - 'a'] = 1;
                    break;
                }
            }
        }
        bool answer = topologicalSort();
        if (answer) {
            for (int i = 0; i < 26; i++) {
                printf("%c", order[i] + 'a');
            }
            printf("\n");
        }
        else {
            printf("INVALID HYPOTHESIS\n");
        }
    }
}