[DFS] 문제 : 고대어 사전

고대어 사전

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • DICTIONARY
  • 1000ms
  • 65536kb
  • 2870
  • 848 (29%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, 아니면 알파벳들의 순서가 영어와 서로 다른 것인지를 알고 싶어합니다.

일리노이 존스는 이 언어에서는 알파벳들의 순서가 영어와 서로 다를 뿐, 사전의 단어들은 사전 순서대로 배치되어 있다는 가설을 세웠습니다. 이 가설이 사실이라고 가정하고, 단어의 목록으로부터 알파벳의 순서를 찾아내려고 합니다.

예를 들어 다섯 개의 단어 gg, kia, lotte, lg, hanhwa 가 사전에 순서대로 적혀 있다고 합시다. gg가 kia보다 앞에 오려면 이 언어에서는 g가 k보다 앞에 와야 합니다. 같은 원리로 k는 l앞에, l은 h앞에 와야 한다는 것을 알 수 있지요. lotte 가 lg 보다 앞에 오려면 o가 g 보다 앞에 와야 한다는 것도 알 수 있습니다. 이들을 종합하면 다섯 개의 알파벳 o, g, k, l, h 의 상대적 순서를 알게 됩니다.

사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 사전에 포함된 단어의 수 N (1 <= N <= 1000) 이 주어집니다. 그 후 N 줄에 하나씩 사전에 포함된 단어가 순서대로 주어집니다. 각 단어는 알파벳 소문자로 구성되어 있으며, 길이는 1 이상 20 이하입니다. 중복으로 출현하는 단어는 없습니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 만약 알파벳들의 순서에 모순이 있다면 "INVALID HYPOTHESIS"를 출력하고, 모순이 없다면 26개의 소문자로 알파벳들의 순서를 출력합니다. 만약 가능한 순서가 여러 개 있다면 아무 것이나 출력해도 좋습니다.

예제 입력

3
3
ba
aa
ab
5
gg
kia
lotte
lg
hanhwa
6
dictionary
english
is
ordered
ordinary
this

예제 출력

INVALID HYPOTHESIS
ogklhabcdefijmnpqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

소스

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Dictionary {
	
	public static int[][] adj;
	public static boolean[] seen = new boolean[26];
	public static List<Integer> order;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("C://dev/sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine().trim());
		for( int testCase = 1; testCase <= T; testCase++ ){
			
			int N = Integer.parseInt(br.readLine().trim());
			String[] words = new String[N];
			for( int i = 0; i < N; i++ ){
				words[i] = br.readLine().trim();
			}
			
			makeGraph(words);
			List<Integer> rt = topologicalSort();
			
			if(rt.isEmpty()){
				bw.write("INVALID HYPOTHESIS");
			}else{
				for(int i=0; i<rt.size(); i++){
					bw.write(Character.toString((char)((int)rt.get(i)+'a')));
				}
			}
			bw.write("\n");
			bw.flush();
			
			
		}
		bw.close();

	}
	
	// 주어진 단어들로부터 알파벳 간의 선후관계 그래프를 생성한다.
	public static void makeGraph(String[] words){
		adj = new int[26][26];
		for(int j = 1; j < words.length; j++){
			int i = j - 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';
					adj[a][b] = 1;
					break;
				}
			}
			
		}
	}
	
	public static void dfs(int here){
		seen[here] = true;
		for( int there = 0; there < adj.length; there++ ){
			if(adj[here][there] == 1 && !seen[there]){
				dfs(there);				
			}
		}
		order.add(here);
	}
	
	public static List<Integer> topologicalSort(){
		int n = adj.length;
		seen = new boolean[n];
		order = new ArrayList<Integer>();
		
		// dfsAll의 역할?
		for(int i=0; i<n; i++){
			if(!seen[i]){
				dfs(i);
			}
		}
		
		Collections.reverse(order.subList(0, order.size()));
		
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				if(adj[order.get(j)][order.get(i)] == 1){
					return new ArrayList<Integer>();
				}
			}
		}
		
		return order;
		
		
	}

}

풀이

1. 위상정렬을 위해 방향 그래프를 만든다.

2. 위상정렬을 dfs로 수행한다.

3. 사이클이 존재하는지 검사. 존재한다면 'INVALID HYPOTHESIS' 출력

4. 결과 출력

adj는 26개 알파벳들의 순서를 나타내는 인접행렬이다.
adj[0][1] == 1 이면 0번 알파멧(a)가 1번 알파벳(b)보다 사전순으로 앞에 온다는 것을 의미한다.
makeGraph 함수에서는 adj 행렬을 만들어 그래프를 생성한다.

dfs 메서드가 리턴하는 순으로 list에 넣으면 위상정렬의 '역'이 된다.
따라서 생성된 위상정렬을 뒤집기 위해 Collections.reverse() 메서드를 사용했음에 주목한다.

위상정렬의 결과는 사이클이 존재할 수 없다. 즉 DAG가 되면 안된다. 만약 사이클이 존재한다면 사전순으로 정렬할 수 없는 input이라고 볼 수 있다.
사이클 여부를 확인하기 위해 이중 for문으로 위상정렬 결과를 검사한다. 만약 사이클이 존재하면 empty list를 리턴해서 분기처리 한다.

#DFS #위상정렬