[그래프] DICTIONARY 고대어 사전

1. 문제

 

고대어 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있지만,

 

사전에 포함된 단어의 순서들이 영어와 서로 다르다.

 

사전선이 다른 순서인지

 

알파벳 순서가 영어와 서로 다른 것인지 알기 위해

 

사전에 포함된 단어들의 목록이 순서대로 주어질 때

 

이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하여라

 

2. DFS, 위상정렬, DAG

 

- 사이클이 없는 방향그래프일때 해당 순서를 계산할 수 있을 것이다.

- DAG를 다루는 문제로 각 알파벳을 정점으로하고 다음문자와의 비교를 통해 알파벳끼리의 간선을 생성할 수 있을 것이다.

 

이 문제는 사이클만 찾는 코드를 구현하면 쉽게 풀 수 있다.

 

사이클이 생기는 경우는 한가지만 체크하면된다.

 

위상정렬을 구하기 위해 dfs를 실행하는 중 함수가 종료될때 정점을  배열에 따로 저장해야한다.

 

이때 만약 u->..->v 와 v-> ..->u 두개의 경로가 있어서 사이클을 만들게되면

 

visited가 true인 상태에서 저장하고 있는 배열에 해당 정점이 없는걸 알 수 있다.

(현재 실행중이므로 같은 경로에 있음을 나타냄, 위상정렬 증명)

 

그러므로 이 부분을 따로 처리해두면 사이클이 없는 방향그래프의 위상정렬을 얻을 수 있다.

 

3. 인접행렬을 이용한 풀이

 

책에서는 인접행렬을 이용하여 문제를 해결하였는데

이는 사이클을 찾는데 더 편리한거 같다.

바로 접근 가능하니 n*n만에 수행가능하다.

 

그러나 인접리스트를 이용하게되면

한개의 인덱스에서 다른 인덱스까지 가는것을 찾으려면

리스트 모두를 또 탐색해야하니 대략 n*n*n의 수행시간이 걸린다.

 

 

인접 리스트를 이용한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
 
using namespace std;
 
int n;
string words[1000];
vector<int> topology;
vector<int> alphabets[26];
vector<int>::iterator iter;
bool visited[26];
int descending;
 
int toNumber(const char& ch)
{
    return ch - 'a';
}
 
void compare(const string& word1, const string& word2)  {
    const char* ch1 = word1.c_str();
    const char* ch2 = word2.c_str();
 
    while((*ch1 == *ch2)&& (*ch1 != '\0' || *ch2 != '\0'))
    {
        ch1++; 
        ch2++;
    }
    if(*ch1 != '\0'&& *ch2 != '\0')
        alphabets[toNumber(*ch1)].push_back(toNumber(*ch2));
}
 
 
bool makeGraph() {
    for(int i = 0; i < n-1; i++)
        compare(words[i], words[i+1]);
    return true;
}
bool dfs(const int& x) {
    visited[x] = true;
    for(int i = 0 ; i < alphabets[x].size(); i++)
        if(visited[alphabets[x][i]]) {
            iter = find(topology.begin(), topology.end(), alphabets[x][i]);
            if(iter == topology.end())  return false;
        }
        else
            if(!dfs(alphabets[x][i])) return false;
    topology.push_back(x);
    return true;
}
 
bool dfsAll() {
    for(int i = 0 ; i < 26; i++) 
        if(!visited[i] && alphabets[i].size()!=0)
            if(!dfs(i)) 
                return false;
    return true;
}
 
void tsort()
{
    reverse(topology.begin(), topology.end());
    for(int i = 0; i < 26; i++)
        if(!visited[i]) 
            topology.push_back(i);
}
 
int main() 
{
    int C;
    cin>>C;
    while(C--) 
    {
        for(int i = 0; i < 26; i++)
            alphabets[i].clear();
        descending = 0;
        topology.clear();
        memset(visited, false, sizeof visited);
 
        cin>>n;
 
        for(int i = 0; i < n; i++) 
            cin>>words[i];
        makeGraph();
        if(!dfsAll())
            cout<<"INVALID HYPOTHESIS\n";
        else 
        {
            tsort();
            for(int i = 0; i < topology.size(); i++) 
                cout<<(char)('a' + topology[i]);
            cout<<"\n";
        }
    }
}

 

4. 문제를 풀면서 한 실수

 

오타 실수: invalid 를 invalif ....

문제 입력범위: 1000개의 단어가 입력으로 나오는데 책에서는 200이였다...

 

 

DICTIONARY