WORDCHAIN - 단어제한 끝말잇기 (오일러 경로, 헤밀토니안 경로)

https://algospot.com/judge/problem/read/WORDCHAIN

헤밀턴 경로 문제를 오일러경로 문제로 바꾸는 것이 포인트.

모든 정점을 지나는 경로->모든 간선을 지나는 경로

https://suuntree.tistory.com/176코드자세한설명

 

 

<문제설명>

단어들이 최대 100개 주어질 때, 이 단어들을 단 한번씩만 이용해서 모든 단어들을 사용할 수 있는지 출력. 사용할 수 있다면 그 순서중 아무거나 출력.

 

<풀이>

모든 단어들을 사용할수 있는지에 대해 그래프를 형성하면, 헤밀토니안 경로를 찾는 문제가 된다.(모든 정점을 정확히 한 번씩 지나는 경로. 외판원 순회(TSP)는 이 경로 중 가장 작은 가중치를 갖는 경로.)

 

헤밀턴 경로를 찾는 유일한 방법은 조합탐색으로 이 문제의 경우 단어 개수 n!만큼의 시간이 걸린다. ->불가능

 

알파벳을 정점으로, 단어를 간선으로 생각한다면 오일러 경로를 찾는 문제가 된다.

 

getEuler에서 파라미터로 벡터를 넘겨 갱신하는 이유는, 함수 자체가 벡터를 반환하는 형태

 

<코드>

int n, adj[26][26], ind[26], oud[26]; //단방향그래프이므로 adj외에 진입진출차수를 유지해야 한다.
vector<string> edge[26][26]; //i에서시작해서 j로 끝나는 단어를 정점 i~j를 잇는 간선으로 본다.

void init() {
	ans.clear();
	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < 26; j++) {
			edge[i][j].clear();
			adj[i][j] = 0;
		}
		ind[i] = oud[i] = 0;
	}	
}

int trailOrCircuit() {
	int s = 0, e = 0;
	for (int i = 0; i < 26; i++) {
		int t = oud[i] - ind[i];		
		if (t == 1) s++;
		if (t == -1)e++;
	}

	if (s == 1 && e == 1) return 1;
	if (s == 0 && e == 0) return 2;
	return 0;
}

vector<int> ans;
void getEuler(int u) {
	for(int v=0; v<26; v++)
		while (adj[u][v] > 0) {
			adj[u][v]--;
			getEuler(v);
		}
	ans.push_back(u);
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		init(); cin >> n;
		vector<string> words(n);
		for (int i = 0; i < n; i++) cin >> words[i];
		for (int i = 0; i < words.size(); i++) {
			int a = words[i][0] - 'a';
			int b = words[i].back() - 'a';
			edge[a][b].push_back(words[i]);
			adj[a][b]++;
			oud[a]++;
			ind[b]++;
		}

		int t = trailOrCircuit();
		if (t == 0) {
			cout << "IMPOSSIBLE\n";
			continue;
		}
		else if (t == 1) { //트레일 가능성
			for (int i = 0; i < 26; i++) 
				if (oud[i] == ind[i] + 1) {
					getEuler(i);
					break; //가능성 있는 시작점 아무데나 하나만 보면 된다.
				}
		}
		else { //서킷 가능
			for(int i=0; i<26; i++)
				if (oud[i]) { 
					getEuler(i);
					break; //가능성 있는 시작점 아무데나 하나만 보면 된다.
				}
		}

		if (ans.size() != n + 1) {
			cout << "IMPOSSIBLE\n";
			continue;
		}

		reverse(ans.begin(), ans.end()); //방향그래프이므로 뒤집어줘야 한다.
		for (int i = 1; i < ans.size(); i++) {
			int a = ans[i - 1], b = ans[i];
			cout << edge[a][b].back() << " ";
			edge[a][b].pop_back();
		}
		cout << '\n';
	}
}

 

<생각>

모든 정점을 지나는 경로에 대한 문제가 모든 간선을 지나는 경로에 대한 문제보다 훨씬 어려운 문제라는 것에 유념.

이 문제처럼 모든 간선에 대한 문제로 바꿔준다면 시간안에 풀 수 있다.