[백준/BOJ] 백준 2848번 : 알고스팟어

www.acmicpc.net/problem/2848

2848번: 알고스팟어

각각 앞뒤 단어를 비교하여 다른 부분을 판단하여 그래프를 만들고, 만들어진 그래프를 이용해 위상 정렬을 하여 문제를 해결하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <map>
using namespace std;

int n;
set<char> all_a;
set<char>::iterator it;
vector<int> adj[26];
vector<int> indegree(26, 0);
vector<string> input;

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

	cin >> n;

	int multi_check = false;
	int not_check = false;

	for (int i = 0; i < n; i++)
	{
		string word;
		cin >> word;

		for (int i = 0; i < word.size(); i++)
			all_a.insert(word[i]);

		input.push_back(word);
	}

	for (int i = 0; i < n - 1; i++)
	{
		int left_size = input[i].size();
		int right_size = input[i + 1].size();

		int compare_len = min(left_size, right_size); //두 단어 중 더 짧은 길이 만큼 비교한다

		for (int j = 0; j < compare_len; j++)
		{
			if (input[i][j] != input[i + 1][j]) //다른 부분을 발견 했을때
			{
				adj[input[i][j] - 'a'].push_back(input[i + 1][j] - 'a');
				indegree[input[i + 1][j] - 'a']++;

				break;
			}

			if (j == compare_len - 1) //마지막 비교까지 왔는데 다른점이 없을때
			{
				if (left_size > right_size) //앞쪽 길이가 더 길때
				{
					not_check = true;
					break;
				}
			}
		}

	}

	//위상 정렬을 이용한다
	queue<int> q;
	for (it = all_a.begin(); it != all_a.end(); it++)
	{
		if (indegree[*it - 'a'] == 0)
			q.push(*it - 'a');
	}

	vector<char> result;

	while (!q.empty())
	{
		if (q.size() != 1) //가능한 순서가 한개 이상일때
			multi_check = true;

		int here = q.front();
		result.push_back(here + 'a');

		q.pop();

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			indegree[there]--;

			if (indegree[there] == 0)
				q.push(there);
		}
	}

	//올바른 순서가 없을때
	if (result.size() != all_a.size())
		not_check = true;

	if (not_check == true)
		cout << "!";
	else if (multi_check == true)
		cout << "?";
	else
	{
		for (int i = 0; i < result.size(); i++)
			cout << result[i];
	}

	return 0;
}