[Algospot] 알고스팟 DICTIONARY 고대어 사전

출처: https://algospot.com/judge/problem/read/DICTIONARY

 Input 

3

3

ba

aa

ab

5

gg

kia

lotte

lg

hanhwa

6

dictionary

english

is

ordered

ordinary

this

 

 Output 

INVALID HYPOTHESIS

ogklhabcdefijmnpqrstuvwxyz

abcdefghijklmnopqrstuvwxyz

 

각 단어들의 알파벳의 선후관계를 통해 위상정렬 (Topological sort) 하는 문제입니다.

위상정렬 (Topological sort)

위상정렬 구현에 앞서 각 단어들의 선후관계를 어떻게 그래프로 표현할지 고민해야 합니다.

bc

bdc

a

단어간의 순서를 통해 b → a 규칙을 알 수 있습니다.

주의할 것은 두번째 단어 'bdc'에서 b → d → c 라고 생각해서는 안됩니다.

단어가 'bdc'일 뿐이지만 알파벳 선후관계를 의미하지 않습니다.

 

'bc'와 'bdc' 두 단어를 비교해보자.

첫 글자가 같기 때문에 c → d 선후 관계를 알 수 있습니다.

'bdc'와 'a'를 비교하면 첫 글자부터 다르므로 b → a라는 정보를 얻을 수 있다.

이렇게 이전 단어와 비교하면서 처음으로 달라지는 지점에서 정보를 얻을 수 있습니다.

 

* 위상정렬 특성상 여러 답이 존재할 수 있는데, 선후관계가 위반하지 않으면

    남은 알파벳은 어떤 순서든 상관 없습니다. (문제상에서 모든 알파벳을 출력해야 한다.)

    ▷ bacdefghij....  / fgbahcjid....

 

* "INVALID HYPOTHESIS"을 출력하는 경우는 그래프가 사이클을 형성하는 경우를 의미합니다.

ba

aa

ab

(비교1) 'ba' vs 'aa'에서 얻어낸 정보 b → a

(비교2) 'aa' vs 'ab'에서 얻어낸 정보 a → b

결국 사이클을 형성하고 있기에 위상정렬할 수 없다.

---

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    static int[][] alpabet;
    static boolean[] finished, visited;
    static Stack<Integer> stack;
    static final int SUCCESS = 1;
    static final int IMPOSSIBLE = 2;
    static int answer;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Test Case 개수
        int T = Integer.parseInt(sc.next());
         
        for(int tc=1; tc<=T; tc++) {
            int N = Integer.parseInt(sc.next());
            alpabet = new int[26][26];
             
            // N >= 1이므로 우선 초기값으로 한개 저장
            String str1 = sc.next();
            for(int i=1; i<N; i++) {
                String str2 = sc.next();
                compare(str1, str2);
                str1 = str2;
            }
             
            visited = new boolean[26];
            finished = new boolean[26];
            stack = new Stack<>();
            // 우선 위상정렬을 할 수 있다고 가정
            answer = SUCCESS;
             
            // 그래프의 모든 지점에 대해 DFS여부를 살피고 탐색한다.
            // (인접행렬이므로 '행'을 기준으로 for문)
            for(int i=0; i<26; i++) {
                // 위상정렬 완료된 정점(알파벳)이라면 pass
                if(finished[i]) continue;
                 
                // 아직 완료되지 않은 정점이라면 DFS를 통해 탐색
                DFS(i);
                // 탐색도중 사이클을 감지한 것.
                if(answer == IMPOSSIBLE) {
                    System.out.println("INVALID HYPOTHESIS");    
                    // Test Case가 여러개이므로 break
                    break;
                }
            }
            if(answer == SUCCESS) {
                // 위상정렬 순 출력
                while(!stack.isEmpty()) {
                    System.out.print((char) (stack.pop() + 97));
                }
                System.out.println();
            }
        }
    }
 
    private static void DFS(int i) {
        // 이번 DFS에서 이미 방문한 곳이면 사이클이 형성된 것
        if(visited[i]) {
            answer = IMPOSSIBLE;
            return;
        }
        // DFS 탐색 중간에 이미 위상정렬 배치가 완료된 정점이라면 pass
        if(finished[i]) return;
         
        // 현재 방문한 곳 표시
        visited[i] = true;
         
        // 현재 정점과 연결된 모든 간선에 대하여 DFS를 하여야 한다.
        for(int j=0; j<26; j++) {
            // 간선이 놓여져 있다면
            if(alpabet[i][j] == 1) {
                // 연결된 지점을 재귀를 통해서 계속해서 타고 들어가게한다.
                DFS(j);    
            }
        }
         
        // 더이상 DFS할 연결된 정점이 없다면 스택에 넣어준다.
        // DFS탐색이 끝났다면 제일 꼬리지점부터 스택에 들어가게된다.
        stack.push(i);
        // 모든 간선을 파악한 것을 의미한다.
        finished[i] = true;
        // 다른 부분 그래프의  DFS할 때 사이클 여부를 확인하기 위해 visited를 초기화 시켜둔다.
        visited[i] = false;
    }
 
    private static void compare(String str1, String str2) {
        // 다른 부분을 찾거나 어느 한쪽의 문자열 길이가 다할 때까지
        int idx = 0;
        while(true) {
            // 어느 한쪽의 문자열이 다 소진될 동안 다른 부분이 없다면 얻어낼 수 있는 정보는 없다.
            // 가령 아래의 경우이다.
            /*
             aaa
             aaab
             */
            if(idx >= str1.length() || idx >= str2.length()) break;
             
            char target1 = str1.charAt(idx);
            char target2 = str2.charAt(idx);
            // 문자가 다르다면
            if(target1 != target2) {
                // 아스키 코드를 이용
                alpabet[target1-97][target2-97] = 1;
                break;
            }
            idx++;
        }
    }
}