백준2848 알고스팟어

작성일 | In

문제 링크

  • http://icpc.me/2848

문제 출처

  • 2010/2011 COCI Contest #6 4번

사용 알고리즘

  • 위상정렬
  • 플로이드 와샬 알고리즘

풀이

N개의 단어가 주어지면 미리 등장하는 알파벳들의 사전순 순서를 저장해둡시다. 이것은 O(N2 * 길이)에 할 수 있습니다.
g[i][j] = 1은 알파벳 i보다 알파벳 j가 뒤에 나와야 한다는 것을 의미할 때, 플로이드 와샬 알고리즘을 돌려주면 모든 알파벳 쌍에 대해 순서를 알 수 있습니다.

만약 g[i][j]와 g[j][i] 모두 1이라면 !를 출력하면 됩니다.
모든 알파벳 K에대해서 g[K][i] = 1인 i의 개수를 저장해둡시다.
단어에 등장한 알파벳이 M개라고 하면, g[K][i] = 1을 만족하는 i의 개수는 0, 1, 2, 3, … , M-1이 나와야 합니다. 그렇지 않다면 ?를 출력해주면 됩니다.

!도 아니고 ?도 아니라면 잘 정렬을 해서 출력하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

int g[33][33];
int chk[33];
vector<int> ch;

void f(string a, string b){
	int sz = min(a.size(), b.size());
	for(int i=0; i<sz; i++){
		if(a[i] == b[i]) continue;
		g[a[i] - 'a'][b[i] - 'a'] = 1;
		return;
	}
	if(a.size() > b.size()){
		cout << "!"; exit(0);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<string> v(n);
	for(auto &i : v) cin >> i;
	for(auto &i : v){
		for(auto j : i){
			chk[j - 'a'] = 1;
		}
	}
	for(int i=0; i<26; i++){
		if(chk[i]) ch.push_back(i);
	}

	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			f(v[i], v[j]);
		}
	}

	for(int k=0; k<33; k++){
		for(int i=0; i<33; i++){
			for(int j=0; j<33; j++){
				if(g[i][k] && g[k][j]) g[i][j] = 1;
			}
		}
	}

	for(int i=0; i<33; i++){
		for(int j=0; j<33; j++){
			if(g[i][j] && g[j][i]){
				cout << "!"; return 0;
			}
		}
	}

	memset(chk, 0, sizeof chk);
	for(int i=0; i<33; i++){
		int cnt = 0;
		for(int j=0; j<33; j++){
			cnt += g[i][j];
		}
		chk[cnt]++;
	}
	for(int i=1; i<ch.size(); i++){
		if(chk[i] != 1){
			cout << "?"; return 0;
		}
	}

	sort(ch.begin(), ch.end(), [](int a, int b){
		return g[a][b];
	});
	for(auto i : ch){
		cout << (char)(i + 'a');
	}
}