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 수열 복원 문제가 어렵다면 코드포스 문제를 먼저 풀어보는 것을 추천한다.

소스 코드 -

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#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; }