알고리즘/알고리즘 문제 해결전략(종만북)

28장 고대어 사전 DICTIONARY

pureworld 2019. 1. 4. 14:50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <queue>
#include <stack>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
 
 
//알파벳의 각 글자에 대한 인접 행렬 표현
//간선 (i,j)는 알파벳 i가 j보다 앞에 와야 함을 나타낸다.
vector<vector<int> > adj;
vector<int> seen, order;
//주어진 단어들로부터 알파벳 간의 선후관계 그래프를 생성한다.
void makeGraph(const vector<string>& words) {
    adj = vector<vector<int> >(26, vector<int>(26, 0));
    for (int j = 1; j < words.size(); j++) {
        int i = j - 1, len = min(words[i].size(), words[j].size());
        //word[i]가 word[j]앞에 오는 이유를 찾는다.
        for(int k=0;k<len;k++)
            if (words[i][k] != words[j][k]) {
                int a = words[i][k] - 'a';
                int b = words[j][k] - '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);
}
//adj에 주어진 그래프를 위상정렬한 결과를 반환한다.
//그래프가 DAG가 아니라면 빈 백터를 반환한다.
vector<int> topologicalSort() {
    int m = adj.size();
    seen = vector<int>(m, 0);
    order.clear();
    for (int i = 0; i < m; i++) if (!seen[i]) dfs(i);
    reverse(order.begin(), order.end());
    //만약 그래프가 DAG가 아니라면 정렬 결과에 역방향 간선이 있다.
    for (int i = 0; i < m; i++)
        for (int j = i + 1; j < m; j++)
            if (adj[order[j]][order[i]])
                return vector<int>();
    //없는 경우라면 깊이 우선 탐색에서 얻은 순서를 반환한다.
    return order;
}
int main(void){
    int cases;
    cin >> cases;
    while (cases--) {
        int n;
        cin >> n;
        vector<string> words;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            words.push_back(s);
        }
        makeGraph(words);
        vector<int> solve = topologicalSort();
        if (solve.empty())
            cout << "INVALID HYPOTHESIS";
        else
            for (int i = 0; i < solve.size(); i++)
                cout << char(solve[i] + 'a');
        cout << "\n";
    }
    return 0;
}
cs

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


위상정렬 문제입니다. dfs를 사용하면 제일 앞에있는 정점이 제일 늦게 종료 된다는 개념을 이용해서

reverse함수를 사용해 뒤집어주면 고대어 단어 사전 정렬이 문제에 알맞게 정렬됩니다.

adj[a][b]가 존재할때 adj[b][a]가 존재한다는 것은 단어의 우선순위에 모순이 있기 때문에 

이 경우에만 빈 벡터를 반환해서 

INVALID HYPOTHESIS를 출력해주시면 됩니다. 





저작자표시 (새창열림)