[알고스팟][C++] WORDCHAIN: 단어 제한 끝말잇기

문제 링크: https://algospot.com/judge/problem/read/WORDCHAIN

(출처: 종만북)

 

Fig 1. 각 단어를 간선으로 갖는 방향그래프

입력에 주어진 각 단어를 간선으로 갖는 방향 그래프를 만들어서, 그 그래프에 오일러 트레일이나 서킷이 존재하는지 확인하면 됩니다. 이때 정점은 알파벳이 되며, 각 단어는 첫글자에서 마지막 글자로 가는 간선이 됩니다.

각 단어를 정점으로 하면 해밀토니안 경로를 구해야 하는데, 모든 조합을 만들어 탐색하면 \(n!\)개의 후보를 만들어야 하고 단어의 수가 최대 100이기 때문에 답을 찾을 수 없습니다.

 

무향 그래프에서 오일러 서킷을 찾는 방법은 이 게시물에서 다뤘는데요, 방향 그래프도 비슷한 방식으로 오일러 서킷을 찾으면 됩니다.

방향그래프의 오일러 서킷에서는 각 정점에 들어오는 간선의 수(indegree)가 나가는 간선의 수(outdegree)와 같아야 합니다.

\begin{align}
outdegree[a] &= indegree[a] + 1 \tag{1} \\
indegree[b] &= outdegree[b] + 1 \tag{2}
\end{align}

방향그래프의 오일러 트레일은 a에서 시작해서 b에서 끝난다고 생각해보면 a에서는 나가는 간선이 들어오는 간선보다 하나 많고, b는 들어오는 간선이 나가는 간선보다 하나 많고, 다른 모든 정점에서는 나가는 간선과 들어오는 간선의 수가 같아야 합니다.

 

조건을 만족하더라도 그래프가 두 개 이상으로 분리된 경우 오일러 서킷, 트레일을 찾을 수 없기 때문에 모든 간선을 방문했는지도 확인해야 합니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


vector<vector<int>> adj;	//인접행렬
vector<string> graph[26][26];	// graph[i][j] = i로 시작해서 j로 끝나는 단어 목록

vector<int> indegree, outdegree;	//i로 시작하는 단어의 수, i로 끝나는 단어의 수

void makeGraph(const vector<string>& words) {
	adj = vector<vector<int>>(26, vector<int>(26));

	for (int i = 0; i < 26; ++i)
		for (int j = 0; j < 26; ++j)
			graph[i][j].clear();

	indegree = outdegree = vector<int>(26);

	// 각 단어를 그래프에 추가
	for (auto& w: words) {
		int a = w.front() - 'a';	// 단어의 앞글자
		int b = w.back() - 'a';		// 단어의 끝글자

		graph[a][b].push_back(w);
		++adj[a][b];
		++outdegree[a];
		++indegree[b];
	}
}

void getEulerCircuit(int current, vector<int>& circuit) {
	for (int next = 0; next < adj.size(); ++next) {
		while (adj[current][next] > 0) {
			--adj[current][next];
			getEulerCircuit(next, circuit);
		}
	}

	circuit.push_back(current);
}

vector<int> getEulerTrailOrCircuit() {
	vector<int> circuit;

	//1. 트레일 -> 시작점 찾아서 시작
	for (int i=0; i<26; ++i)
		if (outdegree[i] == indegree[i] + 1) {
			getEulerCircuit(i, circuit);
			return circuit;
		}

	//2. 서킷 -> 아무데서나
	for (int i=0; i<26; ++i)
		if (outdegree[i]) {
			getEulerCircuit(i, circuit);
			return circuit;
		}

	// 주의 -> 그래프가 여러 컴포넌트로 분리된 경우 정상적으로 반환하는데
	//         전체 그래프의 오일러 트레일, 서킷은 아닐 수 있음

	return circuit;	// 없으면 빈 배열 반환
}

// 오일러 경로 or 트레일인지
bool checkEuler() {
	int plus1 = 0, minus1 = 0;	// 예비 시작점, 끝점의 수
	for (int i = 0; i < 26; ++i) {
		int delta = outdegree[i] - indegree[i];

		//차수는 -1, 1, 0 이어야 함
		if (delta < -1 || 1 < delta) return false;
		if (delta == 1) ++plus1;
		else if (delta == -1) ++minus1;
	}
	
	// 시작점,끝점이 한쌍씩 있거나(트레일), 아니면 하나도 없거나(서킷)
	return (plus1 == 1 && minus1 == 1) || (plus1 == 0 && minus1 == 0);
}

string solve(const vector<string>& words) {
	makeGraph(words);

	if (!checkEuler()) return "IMPOSSIBLE";

	vector<int> circuit = getEulerTrailOrCircuit();

	// 모든 간선을 방문하지 않은 경우
	if (circuit.size() != words.size() + 1) return "IMPOSSIBLE";

	// 방문 순서를 뒤집고, 간선을 모아 문자열로 반환
	reverse(circuit.begin(), circuit.end());
	string ret;
	for (int i = 1; i < circuit.size(); ++i) {
		int a = circuit[i - 1], b = circuit[i];
		if (ret.size()) ret += " ";

		ret += graph[a][b].back();
		graph[a][b].pop_back();
	}
	return ret;
}


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

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<string> words(n);
		for (auto& w : words)
			cin >> w;
		cout << solve(words) << '\n';
	}

	return 0;
}

전체 시간복잡도는 알파벳의 수 A와 단어의 수 n의 곱에 비례하기 때문에 O(nA)가 됩니다.