고대어 사전 - DFS

주어진 단어들을 가지고 DAG를 만들어 위상 정렬 하는 문제이다.

1. 임의의 알파벳 a, b에 대해서 a가 b보다 사전 순으로 앞선다면 a에서 b로 가는 간선이 존재하도록 DAG를 만든다.
2. DFS()가 종료될때마다 리스트에 정점을 넣고 모든 DFS가 끝난 후 리스트를 역순으로 정렬하면 위상 정렬 결과를 얻을 수 있다.
3. DAG에 사이클이 존재한다면 모순이 발생한다. 사이클 발생 여부를 직접 체크할수도 있지만 어차피 위상 정렬을 해야 되기에 간단하게 위상 정렬 후 결과에서 오른쪽에서 왼쪽으로 가는 간선이 있다면 DAG에 사이클이 존재한다는 걸 알 수 있다.

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

public class Main {
    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++) {
            int[][] graph = new int[26][26];
            boolean[] visit = new boolean[26];
            int n = Integer.parseInt(br.readLine());
            String[] words = new String[n];
            for (int i = 0; i < n; i++) { words[i] = br.readLine(); }

            makeGraph(graph, words);
            ArrayList<Integer> result = topologicalSort(graph, visit);
            if(result == null) System.out.println("INVALID HYPOTHESIS");
            else {
                for(int v : result) System.out.print((char)(v + 'a'));
                System.out.println();
            }
        }
    }

    static void makeGraph(int[][] graph, String[] words) {
        for(int i=0; i<words.length - 1; i++) {
            int j = i + 1;
            int len = Math.min(words[i].length(), words[j].length());
            for(int k = 0; k < len; k++) {
                if(words[i].charAt(k) != words[j].charAt(k)) {
                    int a = words[i].charAt(k) - 'a';
                    int b = words[j].charAt(k) - 'a';
                    graph[a][b] = 1;
                    break;
                }
            }
        }
    }

    static ArrayList<Integer> topologicalSort(int[][] graph, boolean[] visit) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < visit.length; i++) if(!visit[i]) dfs(i, graph, visit, list);
        Collections.reverse(list);

        //그래프에 사이클이 있다면 모순 => 위상 정렬 후 오른쪽에서 왼쪽으로 가는 간선이 있다면 모순
        for(int i = 0; i < list.size(); i++) {
            for(int j = i+1; j < list.size(); j++) {
                if(graph[list.get(j)][list.get(i)] == 1) return null;
            }
        }
        return list;
    }

    static void dfs(int v, int[][] graph, boolean[] visit, ArrayList<Integer> list) {
        visit[v] = true;
        for(int i=0; i<graph.length; i++) {
            if(graph[v][i] == 1 && !visit[i]) dfs(i, graph, visit, list);
        }
        list.add(v);
    }
}