[그래프]DFS - 끝말 잇기

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

문제: 

단어들이 주어질 때, 끝말 잇기 순서대로 나열하시오. 불가능하다면 IMPOSSIBLE 출력

예를들어, dog god dragon need 가 주어졌을 때, 끝말 잇기 가능한 순서는 dog god dragon need

풀이:

모든 알파벳을 정점으로 두고, 두 정점간의 관계를 단어의 첫글자와 마지막 글자와의 관계로 지정.

두 정점 사이의 간선은, 해당 알파벳을 첫문자와 마지막 문자로 하는 단어가 됨.

즉 위의 문제 예를 그래프로 표현하면,

프로그램 코드는 다음과 같다.

#include <stdio.h> //printf, scanf

#include <string.h> //strlen

#include <iostream> //cin, cout

#include <vector> //vector

#include <algorithm> //min, max

 

using namespace std;

vector<vector<int>> adj;

vector<string> graph[26][26];

vector<int> indegree, outdegree;

 

void getEulerCircuit(int u, vector<int>& circuit){

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

                  while (adj[u][v]>0){

                           adj[u][v]--;

                           getEulerCircuit(v, circuit);

                  }

         }

         circuit.push_back(u);

}

 

vector<int> getEulerTrailOrCircuit(){

         vector<int> circuit;

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

                  if (outdegree[i] == indegree[i] + 1){

                           getEulerCircuit(i, circuit);

                           return circuit;

                  }

         }

 

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

                  if (outdegree[i]){

                           getEulerCircuit(i,circuit);

                           return circuit;

                  }

         }

 

         return circuit;

}

 

 

void makeGraph(const vector<string>& words){

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

                  for (int j = 0; j < 26; ++j){

                           graph[i][j].clear();

                  }

         }

         adj = vector<vector<int>>(26,vector<int>(26,0));

         indegree = outdegree = vector<int>(26, 0);

 

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

                  int a = words[i][0] - 'a';

                  int b = words[i][words[i].size() - 1] - 'a';

                  graph[a][b].push_back(words[i]);

                  adj[a][b]++;

                  outdegree[a]++;

                  indegree[b]++;

         }

}

 

bool checkEuler(){

         int plus1 = 0, minus1 = 0;

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

                  int delta = outdegree[i] - indegree[i];

                  if (delta < -1 || delta > 1) return false;

                  if (delta == 1) plus1++;

                  if (delta == -1) minus1++;

         }

         return (plus1 == 1 && minus1 == 1) || (plus1==0 && minus1==0);

}

 

string solve(const vector<string>& words){

         makeGraph(words);

         if (!checkEuler()) return "IMPOSSIBLE";

 

         vector<int> circuit = getEulerTrailOrCircuit();

         if (circuit.size() != words.size() + 1) return "IMPOSSIBLE";

 

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

         string ret;

         for (int i = 1; i < circuit.size(); ++i){

                  int a = circuit[i - 1], b = circuit[i];

                  if (ret.size()) ret += " ";

                  ret += graph[a][b].back();

                  graph[a][b].pop_back();

         }

         return ret;

}

 

int main(void){

         freopen("wordchain.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);

                  char ch[11];

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

                           getchar();                        

                           scanf("%s", ch);

                           words[i] = ch;

                  }

 

                  string str = solve(words);

                  printf("%s\n", str.c_str());

         }

         return 0;

}

입력파일

3

4

dog

god

dragon

need

3

aa

ab

bb

2

ab

cd

실행결과

dog god dragon need

aa ab bb

IMPOSSIBLE

계속하려면 아무 키나 누르십시오 . . .

-끝-