28.2 문제: 고대어 사전(문제 ID: DICTIONARY)

28.2 문제: 고대어 사전(문제 ID: DICTIONARY, 난이도: 하)

위상정렬 문제...

위상정렬은 사이클이 없는 방향 그래프, 즉 DAG일 때만 가능한데..

위상정렬이 맞는지 아닌지 체크하는 코딩 방법을 모르고 있었다... 

그래서 헤메다가 책을 보고 역방향 간선이 존재하는지 여부만 체크하면 된다는 것을 알게 되었다.

위상 정렬을 할때는 bfs 를 쓰거나 dfs를 쓰는 두가지 방법이 있다.

이번 문제에서는 dfs 로 위상정렬을 하고 리턴될때마다 저장한 vector를 이용해서 역방향 간선을 체크할 수 있는 방법을 알게됐다.

(bfs로 풀때 위상정렬 체크하는 방법도 알아놔야 겠다!)

원래는 그냥 스택에 넣고 출력만 했었는데, 위상정렬을 한번 더 체크하려니 조금 복잡했었다.

책에서는 이차원 배열같이 해서 풀었는데 나는 vector 를 써서 확인하는데 3중 for문을 사용했다..

이렇게 범위가 작을 때는 인접행렬이 더 좋아 보인다.. 내 코드가 조금 복잡해 보일 수도 있다..

나중에 다시 풀어볼 만한 문제인 것 같다.

<정답 코드>

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
 
int tc, N;
vector<string> words;
vector<int> v[26];
vector<int> order;
bool visited[26];
bool isCycle;
void dfs(int s)
{
    visited[s] = true;
 
    for (int i = 0; i < v[s].size(); i++)
    {
        int next = v[s][i];
        if (!visited[next])
        {
            dfs(next);
        }
    }
 
    order.push_back(s);
 
    return;
}
int main()
{
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        isCycle = false;
        words.clear();
        order.clear();
        memset(visited, false, sizeof(visited));
        
 
        for (int i = 0; i < 26; i++)
        {
            v[i].clear();
        }
 
        cin >> N;
        cin.ignore();
 
        for (int i = 0; i < N; i++)
        {
            string s;
            getline(cin, s);
            words.push_back(s);
        }
 
        //그래프 만들기
 
        for (int i = 0; i < N - 1; i++)
        {
            for (int j = 0; j<min(words[i].size(),words[i+1].size()) ; j++)
            {
                if (words[i][j] != words[i + 1][j])
                {
                    v[words[i][j] - 'a'].push_back(words[i + 1][j]-'a');
                    break;
                }
            }
        }
 
        //위상정렬
        for (int i = 0; i < 26; i++)
        {
            if (!visited[i])
            {
                dfs(i);
            }
        }
 
 
        //위상정렬 위배되는지 확인
        for (int i = 0; i < order.size()-1; i++)
        {
            for (int j = i+1; j < order.size(); j++)
            {
                for (int k = 0; k < v[order[i]].size(); k++)
                {
                    if (v[order[i]][k] == order[j])
                    {
                        isCycle = true;
                        break;
                    }
                }
 
                if (isCycle)
                {
                    break;
                }
            }
 
            if (isCycle)
            {
                break;
            }
 
        }
 
 
        //정답 출력
        if (isCycle)
        {
            cout << "INVALID HYPOTHESIS" << endl;
        }
        else
        {
            reverse(order.begin(), order.end());
 
            for (int i = 0; i < order.size(); i++)
            {
                cout << (char)(order[i]+'a');
            }
            cout << endl;
        }
 
    }
 
    return 0;
}