BOJ 1591 - 수열 복원

분류 - [ 오일러 경로 ]

전형적인 문제다. N-M+1 개의 수열에 대해 앞 정점(M개에서 맨 뒤만 빠진 배열)과 뒷 정점(M개에서 맨 앞만 빠진 배열)을 이어주고, 이 그래프에서 오일러 회로 및 경로를 찾는다(입력에 따라 회로인지 경로인지 판단해야 한다).

다만 좀 까다롭다는 점은 정점이 담아야하는 것이 배열이기 때문에 이를 유의하여 소스를 짜주시면 되겠다.

좀 더 쉬운 버전의 문제로는 

Tanya and Password (http://codeforces.com/contest/508/problem/D)

이 문제는 http://coloredrabbit.tistory.com/37?category=729843에 해설도 적어놓았으니, BOJ 1591 수열 복원 문제가 어렵다면 코드포스 문제를 먼저 풀어보는 것을 추천한다.

소스 코드 -

#include <cstdio>
#include <deque>
#include <map>
#include <vector>
using namespace std;
using DT = long long;
const int MAX_V = 1011;

map<deque<DT>, int> vertices;
deque<DT> edges[MAX_V];
DT endN[MAX_V];
int vn;
vector<int> adj[MAX_V];
int getV(deque<DT>& s, int mod, deque<DT> origin) {
	int cur_vn = -1;
	if (vertices.find(s) != vertices.end())
		cur_vn = vertices[s];
	if (cur_vn != -1 && edges[cur_vn].size() == 0 && mod == 1)
		edges[cur_vn] = origin;

	if (cur_vn == -1) {
		vn++;
		cur_vn = vn;
		endN[cur_vn] = s.back();
		if(mod == 1) 
			edges[cur_vn] = origin;
		return vertices[s] = cur_vn;
	}	
	return vertices[s];
}

vector<int> c;
void dfs(int u) {
	while (adj[u].size()) {
		int v = adj[u].back();
		adj[u].pop_back();
		dfs(v);
	}
	c.push_back(u);
}

int main() {
	int N, M, i, j, sn, u, v, ind[MAX_V] = {}, outd[MAX_V] = {}, f = 1, startV;
	scanf("%d%d", &N, &M);
	sn = N - M + 1;
	deque<deque<DT>> seqs(sn, deque<DT>(M));
	deque<DT> tmp,dummy;

	for (i = 0; i < sn; i++)
		for (j = 0; j < M; j++)
			scanf("%lld", &seqs[i][j]);
	
	for (i = 0; i < sn; i++) {
		tmp = seqs[i];
		tmp.pop_back();
		u = getV(tmp, 1, seqs[i]);
		
		tmp.push_back(seqs[i].back());
		tmp.pop_front();
		v = getV(tmp, 0, dummy);

		adj[u].push_back(v);
		outd[u]++;
		ind[v]++;
	}

	for(i=0; i <= vn && f;i++)
		if (outd[i] == ind[i] + 1) {
			dfs(startV = i);
			f = 0;
		}
	for (i = 0; i <= vn && f; i++)
		if (outd[i]) {
			dfs(startV = i);
			f = 0;
		}
	for (i = 0; i < (int)edges[startV].size() - 1; i++)
		printf("%lld ", edges[startV][i]);
	for (i = c.size() - 2; i >= 0; i--)
		printf("%lld ", endN[c[i]]);

	return 0;
}