백준1591 수열 복원

작성일 | In

문제 링크

  • http://icpc.me/1591

사용 알고리즘

  • 오일러 회로/경로

풀이

수열을 적당히 이어 붙여서 원본 수열을 만들어야 합니다.
원본 수열이 주어진 수열을 모두 지난다는 점에서 모든 정점을 방문하는 해밀턴 경로나 모든 간선을 방문하는 오일러 경로를 생각해볼 수 있습니다. 해밀턴 경로 문제는 NP-Complete 문제이므로 오일러 경로 관련 풀이를 생각해봅시다.

주어진 두 수열을 잘 연결하고, 그 연결하는 간선들을 모두 봤을 때 원본 수열이 나오도록 만들면 됩니다.
주어진 수열 $A$에서 맨 뒷 글자만 잘라낸 수열 $X = A[:-1]$과 맨 앞 글자만 잘라낸 수열 $Y = A[0:]$을 생각해봅시다. 원본 수열에서, $X$ 바로 뒤에 $Y$가 나오는 부분 수열이 존재해야 합니다. 그러므로 $X$에서 $Y$로 가는 간선을 만들고 오일러 회로/경로를 구하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int N, M, pv;
map<vector<int>, int> ID;
vector<int> Rev[1010];
int In[1010], Out[1010], G[1010][1010];

vector<int> Path;

void DFS(int v){
    for(int i=1; i<=pv; i++) while(G[v][i]) G[v][i]--, DFS(i);
    Path.push_back(v);
}
void Get(){
    for(int i=1; i<=pv; i++) if(In[i] < Out[i]){ DFS(i); return; }
    for(int i=1; i<=pv; i++) if(Out[i]){ DFS(i); return; }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N-M+1; i++){
        vector<int> a, b;
        for(int j=1; j<=M; j++){
            int t; cin >> t;
            if(j != M) a.push_back(t);
            if(j != 1) b.push_back(t);
        }
        if(!ID.count(a)) ID[a] = ++pv, Rev[pv] = a;
        if(!ID.count(b)) ID[b] = ++pv, Rev[pv] = b;
        int s = ID[a], e = ID[b];
        Out[s]++; In[e]++; G[s][e]++;
    }
    Get();
    reverse(Path.begin(), Path.end());

    for(auto i : Rev[Path[0]]) cout << i << " ";
    Path.erase(Path.begin());
    for(auto i : Path) cout << Rev[i].back() << " ";
}