BOJ 1591 - 수열 복원

문제 링크 : https://www.acmicpc.net/problem/1591

문제 풀이

 맨 처음에 같은 숫자의 가능성을 생각하지 못하고, 배열에서 인접한 두 값을 통해서 순서 관계를 얻을 수 있기 때문에 이를 조합하여 위상정렬을 하면 될 것이라고 생각했다. 그래서 코딩을 바로 했고, 틀린 후에 같은 숫자의 가능성을 생각해냈다. 

 일정 시간동안 생각을 했음에도 풀이를 생각해 낼 수 없었고, 태그를 열어봤더니 오일러 경로가 있었다... 몰랐던 내용이었기 때문에 풀이를 보았다. 

 길이 m-1 개의 배열로 잘라서 생각한다. 그 m-1 길이의 배열간의 배치 순서를 모두 알 수 있다면 문제를 해결할 수 있다. 문제에서 주어지는 길이 m의 배열은 길이 m-1 배열 두 개의 인접한 순서 관계를 알려준다. 정확히는 맨 마지막 값을 제외한 m-1 길이의 수열 다음에 맨 앞의 값을 제외한 길이 m-1 배열이 등장한다는 것을 알려준다. 

 이렇게 알려준 모든 순서관계를 따라서 순회 해야 하기 때문에 이 문제를 오일러 회로를 이용해야 한다고 생각할 수 있다. 각 m-1 길이의 배열을 정점으로 치환하면, 문제에서 주어지는 정보는 간선이 되고, 이를 따라서 오일러 경로를 찾아주면 된다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
#define all(v) v.begin(), v.end()
 
ll arr[1010101];
vector<ll> v[10101];
vector<ll> brr[10101];
vector<vector<ll>> vst;
ll nxt[10101];
ll ind[10101];
ll oud[10101];
ll cnt[10101];
vector<ll> pth;
 
ll n,m,sz;
 
void dfs(ll x){
    while(v[x].size()){
        ll p=v[x][v[x].size()-1];
        v[x].pop_back();
        dfs(p);
    }
    pth.push_back(x);
}
void get(){
    for(ll i=1; i<=sz; i++) if(ind[i] < oud[i]){ dfs(i); return; }
    for(ll i=1; i<=sz; i++) if(oud[i]){ dfs(i); return; }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll i,j,k,l;
    cin>>n>>m;
    for(i=1;i<=n-m+1;i++){
        for(j=1;j<=m;j++) {
            ll x;
            cin>>x;
            if(j!=m) brr[i*2-1].pb(x);
            if(j!=1) brr[i*2].pb(x);
        }
        vst.pb(brr[i*2-1]);
 
        vst.pb(brr[i*2]);
    }
 
    sort(vst.begin(), vst.end());
    vst.erase(unique(vst.begin(), vst.end()),vst.end());
 
    for(i=1;i<=n-m+1;i++){
        ll x1=lower_bound(vst.begin(), vst.end(),brr[i*2-1])-vst.begin()+1;
        ll x2=lower_bound(vst.begin(), vst.end(),brr[i*2])-vst.begin()+1;
        v[x1].pb(x2);
        oud[x1]++;
        ind[x2]++;
        cnt[x1]++;
        cnt[x2]++;
    }
 
    sz=vst.size();
    get();
 
    reverse(pth.begin(), pth.end());
 
    ll psz=pth.size();
    for(i=0;i<psz-1;i++){
        cout<<vst[pth[i]-1][0]<<' ';
    }
 
    for(auto k:vst[pth[psz-1]-1]){
        cout<<k<<' ';
    }
    
 
}