단어 제한 끝말잇기 - DFS

문제를 방향 그래프로 만들어 오일러 경로 또는 오일러 트레일을 구하는 문제로 변환할 수 있다. a부터 z를 정점으로 두고 단어의 시작 알파벳에서 단어의 마지막 알파벳으로 가는 간선을 추가한다. 예를 들어 dog 단어가 나온다면 d에서 g로 가는 간선을 추가한다. 그런 다음 방향 그래프에 오일러 경로 혹은 트레일이 존재할 수 있는지 확인 후 오일러 경로 또는 오일러 트레일을 구해 단어를 출력한다.

• (모든 정점) 진입 차수 = 진출 차수 → 오일러 경로 존재
• (시작점) 진출 차수 = 진입 차수 + 1, (끝점) 진출 차수 = 진입 차수 - 1, (나머지 정점) 진입 차수 = 진출 차수 → 오일러 트레일 존재

import java.util.*;
import java.io.*;

public class Main {
    static int[][] graph;
    static int[] inDegree;
    static int[] outDegree;
    static ArrayList<String>[][] words;
    static ArrayList<String> input;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int testCase = Integer.parseInt(br.readLine());
        for (int t = 0; t < testCase; t++) {
            graph = new int[26][26];
            inDegree = new int[26];
            outDegree = new int[26];
            words = new ArrayList[26][26];
            for (int i = 0; i < 26; i++)
                for (int j = 0; j < 26; j++) words[i][j] = new ArrayList<>();

            int count = Integer.parseInt(br.readLine());
            input = new ArrayList<>();
            for (int i = 0; i < count; i++) input.add(br.readLine());

            InitGraph();
            System.out.println(solve());
        }
    }

    static void InitGraph() {
        for (String word : input) {
            int start = word.charAt(0) - 'a';
            int end = word.charAt(word.length() - 1) - 'a';
            graph[start][end]++;
            inDegree[end]++;
            outDegree[start]++;
            words[start][end].add(word);
        }
    }

    static void getEulerCircuit(int v, ArrayList<Integer> list) {
        for (int i = 0; i < 26; i++) {
            if (graph[v][i] > 0) {
                graph[v][i]--;
                getEulerCircuit(i, list);
            }
        }
        list.add(v);
    }

    static ArrayList<Integer> getEulerTrailOrCircuit() {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (outDegree[i] == inDegree[i] + 1) {
                getEulerCircuit(i, list);
                return list;
            }
        }
        for (int i = 0; i < 26; i++) {
            if(outDegree[i] > 0) {
                getEulerCircuit(i, list);
                return list;
            }
        }
        return list;
    }

    static String solve() {
        //오일러 트레일 또는 오일러 서킷이 존재/여부 확인
        int plus1 = 0, minus1 = 0;
        for(int i=0; i<26; i++) {
            int delta = outDegree[i] - inDegree[i];
            if(delta < -1 || 1 < delta) return "IMPOSSIBLE";
            if(delta == 1) plus1++;
            if(delta == -1) minus1++;
        }
        if(!((plus1 == 0 && minus1 == 0) || (plus1 == 1 && minus1 == 1))) return "IMPOSSIBLE";

        //경로 탐색
        ArrayList<Integer> result;
        result = getEulerTrailOrCircuit();

        //아직 간선이 남아있다면 IMPOSSIBLE
        if(result.size() != input.size() + 1) return "IMPOSSIBLE";

        Collections.reverse(result);
        StringBuilder str = new StringBuilder();
        for(int i = 0; i < result.size() - 1; i++) {
            str.append(words[result.get(i)][result.get(i + 1)].get(0));
            str.append(" ");
            words[result.get(i)][result.get(i+1)].remove(0);
        }
        return str.toString();
    }
}