[그래프]DFS - 위상 정렬

점들간에 순서 의존성이 있을 때, 이 의존성을 고려해서 정렬하는 것은 위상정렬(topological sorting)이라고 한다.

예를 들어, 5명 애들에 대해 두 명씩 키를 비교한 자료가 다음과 같다고 하자.

A > B

B > C

C > D

D > E

이러한 자료를 근거로해서 키 순서대로 정렬한다면 A > B > C > D > E가 될 것이고, 이러한 정렬을 위상정렬이라한다.

방향성이 있는 그래프에서, 이 방향성을 고려한 정렬은 어떻게 하면 될까?

답은, DFS로 모든 점에 대해서 탐색을 하면서, dfs()함수가 종료될 때마다 해당 정점을 기록하고, 이 정점들을 역으로 뒤집으면 됨.

void dfs(int u){

         visited[u] = 1;

         for (int v = 0; v < adj[u].size(); ++v){            

                  if (adj[u][v] && !visited[v])      dfs(v);

         }

         ordered.push_back(u);

}

관련문제: Dictionary https://algospot.com/judge/problem/read/DICTIONARY

입력으로 단어들이 주어지고, 이 단어들의 순서가 사전상의 순서라고 했을 때, 이 단어들의 순서에 부합하는 새로운 알파벳 순서 출력하기.

풀이 코드

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

 

using namespace std;

 

vector<vector<int>> adj;

vector<int> visited;

vector<int> ordered;

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;

                  int len = min(words[i].size(), words[j].size());

                  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 u){

         visited[u] = 1;

         for (int v = 0; v < adj[u].size(); ++v){            

                  if (adj[u][v] && !visited[v])      dfs(v);

         }

         ordered.push_back(u);

}

 

vector<int> topologicalSort(void){

         int n = adj.size();

         visited = vector<int>(n, 0);

         ordered.clear();

         for (int i = 0; i < adj.size(); ++i) if (!visited[i])         dfs(i);

         reverse(ordered.begin(), ordered.end());

 

         for (int i = 0; i < n; ++i){

                  for (int j = i + 1; j < n; ++j){

                           if (adj[ordered[j]][ordered[i]])

                                   return vector<int>();

                  }

         }

         return ordered;

}

 

int main(void){  

         //freopen("dictionary.txt", "r", stdin);

         setbuf(stdout, NULL);     

 

         int C, N;

         cin >> C;

 

         for (int test = 1; test <= C; ++test){

                  cin >> N;

                  vector<string> words = vector<string>(N);

 

                  getchar();

                  for (int i = 0; i < N; ++i){

                           getline(cin, words[i]);

                  }

                  makeGraph(words);

                  vector<int> ret = topologicalSort();       

 

                  if (ret.size() == 0){

                           printf("INVALID HYPOTHESIS");

                  }

                  else{

                           for (int i = 0; i < ret.size(); ++i){

                                   printf("%c", ret[i] + 'a');

                           }

                  }

                 

                  printf("\n");

         }

        

}

[입력] 

3
3
ba
aa
ab
5
gg
kia
lotte
lg
hanhwa
6
dictionary
english
is
ordered
ordinary
this

출력

INVALID HYPOTHESIS

zyxwvutsrqponmjigklhfedcba

zyxwvusrqpnmlkjhgfdeiotcba

-끝-