[BOJ 16182] Dumae

https://www.acmicpc.net/problem/16182

16182번: Dumae

Tag : Topological Sort, Greedy, Path Compression

 

문제 요약

위상정렬 순서에 어긋나지 않게 자리를 배치하는데, 각 사람은 \([L_i,R_i]\)구간에 있어야 한다. 이것이 불가능한 경우에는 -1출력, 가능하다면 첫번째부터 N번째까지 위치한 사람의 번호를 순서대로 출력.

 

풀이

위상정렬에 대한 조건없이 구간에 대한 조건만 존재한다면 8/14일에 열린 ABC 214 E번과 동일한 그리디로 풀이할 수 있다. \(R\)순으로 오름차순 정렬 후 구간 내에서 사용되지 않은 가장 왼쪽으로 보내면 된다. 가장 왼쪽으로 보내지 않은 최적해가 존재하고 왼쪽을 쭉 비워놓는다면 이를 왼쪽으로 보내도 최적해가 깨지지 않는다라는 것으로 증명해볼 수 있겟다. 엄밀한 증명은 ABC 214의 에디토리얼을 읽어보자. 구간 내에서 채워지지 않은 가장 왼쪽 자리를 어떻게 찾냐는 문제는 Dynamic Segment Tree 또는 PathCompression을 통해 해결할 수 있다. \(DST\)는 구현이 굉장히 화나기 때문에(당장 이 문제를 풀기 몇시간 전에 당해버렷....) 두번째 방법을 선택했다. \(pa_i = i\)이상인 가장 왼쪽 빈자리를 가리킨다고 해보자. \(pa_i = i\)라면 \(i\)는 빈자리이고 그렇지 않다면 계속 경로를 따라가주면 된다. 이를 구현하면 \(DSU\)와 흡사한 형태를 띈다.  

 

이제 어떻게 하면 위상정렬의 조건을 제거할 수 있을지 생각해보자. x->y의 간선이 존재한다면 \(L_y=max(L_y,L_x+1), R_x=min(R_x,R_y-1)\)로 바꾸어주자. 어떤 방법을 사용하더라도 \(y\)는 \(L_x+1\)이상의 위치에 들어가게 된다. \(x\)도 자리에 들어가야하기 때문이다. 반대로 \(y\)도 무조건 자리에 들어가야하기 때문에 \(R_x\)는 \(R_y-1\)이하가 된다.

 

이렇게 \(L,R\)을 새롭게 구성해주면 위상정렬의 조건을 신경쓰지 않아도 된다. 나와 비요뜨는 \(R_x\)는 역순 간선으로 위상정렬하며 갱신해야 잘 반영된다는 것을 인지하지 못하고 코드를 작성했다가 5%에서 무한 WA를 맞았다... 이 문제를 풀게 된다면 이 점을 주의하자. 

 

전체 코드  

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;

int N, M;
int L[303030], R[303030];
int pa[303030], ans[303030];
int indegree[303030], rindegree[303030];
int dep[303030];
vector<int> v[303030], g[303030];

int find(int a){
    if(a == pa[a]) return a;
    else return pa[a] = find(pa[a]);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> N >> M;
    for(int i = 1; i<=N; i++) cin >> L[i] >> R[i];
    for(int i = 1,x,y; i<=M; i++){
        cin >> x >> y;
        v[x].pb(y); g[y].pb(x);
        indegree[y]++; rindegree[x]++;
    }
    queue<int> q;
    for(int i = 1; i<=N; i++) if(indegree[i]==0) q.push(i);
    while(q.size()){
        int cur = q.front(); q.pop();
        for(auto &i : v[cur]){
            L[i]=max(L[i],L[cur]+1);
            if(--indegree[i]==0) q.push(i),dep[i]=dep[cur]+1;
        }
    }
    int f = 0; for(int i = 1; i<=N; i++) if(indegree[i]!=0) f=1;
    if(f) return cout << -1 << endl, 0;
    for(int i = 1; i<=N; i++) if(rindegree[i]==0) q.push(i);
    while(q.size()){
        int cur = q.front(); q.pop();
        for(auto &i : g[cur]){
            R[i]=min(R[i],R[cur]-1);
            if(--rindegree[i]==0) q.push(i);
        }
    }
    struct P{ int l, r, id; };
    vector<P> sec(N);
    for(int i = 1; i<=N; i++) sec[i-1]={L[i], R[i], i};
    sort(all(sec), [&](P &a, P &b){ return a.r < b.r; });
    for(int i = 1;i<=N; i++) pa[i]=i;
    for(auto &[i,j,id]:sec){
        int p=find(i);
        if(p>j or p<i) return cout<< -1 << endl, 0;
        ans[p]=id;
        pa[p]=p+1;
    }
    for(int i = 1; i<=N; i++) cout << ans[i] << endl;
}