[백준 2848] 알고스팟어

문제 링크 => 2848번: 알고스팟어 (acmicpc.net)

2848번: 알고스팟어

---

위상정렬 문제이다.

 

알고스팟어의 알파벳 사전 순으로 정렬되어 있는 단어의 목록이 주어질 때, 알고스팟어의 알파벳을 순서대로 구해야 하는 문제이다.

 

접근 방법은 다음과 같다.

 

1. 문자열들의 모든 경우를 각각 2개씩 비교하면서 확실하게 알파벳의 순서가 변경되는 지점을 찾고 위상정렬을 위한 inDegree 세팅을 해준다.

알파벳의 순서가 변경되는 지점을 찾는 방법을 예제 입력 1 을 통해서 알아보도록 한다.

 

s1 : ula, s2 : uka => s1[1], s2[1] 에서 달라지는 것을 확인, 따라서 s1[1] < s2[1] 이므로 l 다음에 k 임을 알 수 있음

s1 : ula, s2 : kula => s1[0], s2[0] 에서 달라지는 것을 확인, 따라서 s1[0] < s2[0] 이므로 u 다음에 k 임을 알 수 있음

...

 

위 방법을 정리해보자면, 문자열 s1, s2의 index = 0 을 기준으로 비교해가면서 특정 index에서 문자가 다를 경우 각 문자를 x, y라고 할 때 x => y 가 되도록 위상정렬 세팅을 해준다.

 

주의할 점! => 다음과 같은 경우를 조심해야 한다.

 

s1 : abcde, s2 : abc => c까지 동일한 경우 s1이 s2보다 길이가 길어서 올바른 사전 순으로 배치된 경우가 아니므로 올바른 순서를 정할 수 없다.

s1 : abc, s2 : abc => 이 경우도 마찬가지로 c까지 동일하며 s1와 s2 길이가 동일하므로 올바른 사전 순으로 배치된 경우가 아니므로 올바른 순서를 정할 수 없다.

 

즉, prefix가 동일한 경우 s1의 길이가 s2의 길이보다 길거나 같은 경우 순서를 정할 수 없다는 것을 파악해야 한다. (이부분 때문에 많은 시간을 써먹을 뻔 했으나 친절하게 질문 검색에 나와있어서 금방 해결하였음)

 

2. 세팅된 inDegree 값이 0이 되는 문자를 Queue에 push 하고 다음을 고려한다.

 

알고스팟어의 단어 갯수만큼 for문을 진행하면서  

(1)  Queue의 size가 1보다 큰 경우 => marko, darko, zarko 와 같은 경우라고 볼 수 있다. 즉, arko가 전부 동일하므로 inDegree값이 0이 될 것이며 진입차수가 0인 문자가 여러개라는 말은 결국 가능한 순서가 한 개 이상이므로 "?" 을 출력하도록 한다.

 

(2) Queue의 size가 0이되는 경우 => 단어 갯수만큼 알고스팟어의 알파벳 순서를 결정하지 못한다면 이건 올바른 순서가 없는 경우이므로 "!" 을 출력하도록 한다.

 

(3) 정상적으로 for문을 마친 경우 진입차수가 0일때 push한 각 문자들을 순서대로 나열한다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int n, word_Total;
int inDegree[26];
string s[101];
vector<int> v[26];
vector<char> result;
map<char, int> word;
map<pair<char, char>, int> pair_Word;

void count_Word() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < s[i].size(); j++) {
			char c = s[i][j];
			if (!word[c]) {
				word[c] = 1;
				word_Total++;
			}
		}
	}
}

int get_InDegree() {
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int size = min(s[i].size(), s[j].size());
			for (int k = 0; k < size; k++) {
				char x = s[i][k], y = s[j][k];
				if (x != y) {
					if (!pair_Word[{x, y}]) {
						pair_Word[{x, y}] = 1;
						inDegree[y-'a']++;
						v[x-'a'].push_back(y-'a');
					}
					break;
				}
				if (k == size - 1 && s[i].size()>s[j].size()) {
					return 1;
				}
			}
		}
	}
	return 0;
}

void is_Algospat_Language() {
	queue<int> q;

	for (char ch = 'a'; ch <= 'z'; ch++) {
		if (word[ch] && inDegree[ch-'a'] == 0) {
			q.push(ch-'a');
			result.push_back(ch);
		}
	}

	for (int i = 0; i < word_Total; i++) {
		if (q.size() > 1) {
			cout << "?";
			return;
		}
		if (q.size() == 0) {
			cout << "!";
			return;
		}
		int x = q.front();
		q.pop();
		for (int j = 0; j < v[x].size(); j++) {
			int next = v[x][j];
			if (--inDegree[next] == 0) {
				char c = next + 'a';
				result.push_back(c);
				q.push(next);
			}
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
	}
}

void solve() {

	// 나온 문자 전부 세기
	count_Word();

	// 진입차수 설정
	if (get_InDegree()) {
		cout << "!";
		return;
	}

	// 알고스팟어 판단
	is_Algospat_Language();

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	solve();

	return 0;
}