[ALGOSPOT] 단어 제한 끝말잇기 (WORDCHAIN)

출처 : algospot.com/judge/problem/read/WORDCHAIN

algospot.com :: WORDCHAIN

<문제>

끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서 사용할 수 있는 단어들의 목록이 주어질 때, 단어들을 전부 사용하고 게임이 끝날 수 있는지, 그럴 수 있다면 어떤 순서로 단어를 사용해야 하는지를 계산하는 프로그램을 작성하세요.

 

<입력>

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 게임에서 사용할 수 있는 단어의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에 하나씩 게임에서 사용할 수 있는 단어가 주어집니다. 각 단어는 알파벳 소문자로 구성되어 있으며, 길이는 2 이상 10 이하입니다. 중복으로 출현하는 단어는 없습니다.

 

<출력>

각 테스트 케이스마다 한 줄을 출력합니다. 만약 모든 단어를 사용하고 게임이 끝나는 방법이 없다면 "IMPOSSIBLE" 을 출력하고 (따옴표 제외), 방법이 있다면 사용할 단어들을 빈 칸 하나씩을 사이에 두고 순서대로 출력합니다. 방법이 여러 개 있다면 그 중 아무 것이나 출력해도 좋습니다.

 

<예제 입력>

3

4

dog

god

dragon

need

3

aa

ab

bb

2

ab

cd

 

<예제 출력>

need dog god dragon

aa ab bb

IMPOSSIBLE

 

 

오일러 서킷, 오일러 트레일을 이용한 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
void get_path(int startv, vector<int>& circuit, vector<int>&indegree,
                    vector<int>& outdegree, vector<vector<int>>& graph)
{
    for(int i=0;i<26;i++)
    {
        while(graph[startv][i])
        {
            graph[startv][i]--;
            get_path(i, circuit, indegree, outdegree, graph);
        }
    }
    circuit.push_back(startv);
}
 
vector<int> trail_or_circuit(vector<int>& indegree, 
    vector<int>& outdegree, vector<vector<int>>& graph)
{
    vector<int> circuit;
    for(int i=0;i<26;i++)
    {
        if(indegree[i] == outdegree[i]+1)
        {
            get_path(i, circuit, indegree, outdegree, graph);
            return circuit;
        }
    }
    for(int i=0;i<26;i++)
    {
        if(outdegree[i])
        {
            get_path(i, circuit, indegree, outdegree, graph);
            return circuit;
        }
    }
    return circuit;
}
 
bool check(vector<int>& indegree, vector<int>& outdegree)
{
    int startv = 0, endv = 0;
    for(int i=0;i<26;i++)
    {
        int sub = outdegree[i]-indegree[i];
        if(sub < -1 || sub > 1) return false;
        if(sub == 1) startv++;
        if(sub == -1) endv++;
    }
    if(startv == 1 && endv == 1) return true;
    if(startv == 0 && endv == 0) return true;
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin >> tc;
    while(tc--)
    {
        int n;
        cin >> n;
        vector<string> v[26][26];
        vector<int> indegree(26, 0), outdegree(26, 0);
        vector<vector<int>> graph(26, vector<int>(26, 0));
        string tmp;
        for(int i=0;i<n;i++)
        {
            cin >> tmp;
            int startv = tmp.front()-'a', endv = tmp.back()-'a';
            v[startv][endv].push_back(tmp);
            indegree[startv]++;
            outdegree[endv]++;
            graph[startv][endv]++;
        }
        if(!check(indegree, outdegree))
        {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        vector<int> ans = trail_or_circuit(indegree, outdegree, graph);
        reverse(ans.begin(), ans.end());
        for(size_t i=1;i<ans.size();i++)
        {
            cout << v[ans[i-1]][ans[i]].back() << ' ';
            v[ans[i-1]][ans[i]].pop_back();
        }
        cout << endl;
    }
    return 0;
}