BOJ 11738 - Distance on Triangulation

문제 링크 : www.acmicpc.net/problem/11738

문제 설명

다각형이 삼각분할 되어있다. 모든 선분의 길이는 1이다. 쿼리로 두 점이 주어졌을 때 두 점 사이의 거리를 출력하는 문제이다. 

문제 태그

bfs, dnc, offline query, 재귀

문제 풀이

이 문제를 보면 가장 먼저 $O(NM)$ 의 풀이를 생각할 수 있다. 본인은 n개의 점에서 모두 다익스트라를 돌려서 $O(NMlgN)$의 풀이를 생각했지만 모든 선분의 가중치가 1이기 때문에 모든 점을 시작점으로 해서 각각 bfs를 하는 것으로 $O(NM)$의 풀이가 나오게 된다. 하지만 문제에서 요구하는 시간 복잡도는 제곱 미만이다. 따라서 이 문제의 특성을 관찰해야 한다.

이 문제의 가장 큰 특성은 일반적인 그래프가 아닌 삼각분할된 다각형 위에서 진행이 된다는 것이다. 
여기서 핵심적인 관찰을 진행해보자 어떤 다각형을 삼각분할의 대각선중 한 대각선으로 분리한다고 해보자. 만약 두개의 점이 분리된 서로 다른 도형에 속해있다면, 그 두 점 사이를 가기 위해서는 대각선의 양끝점 중 하나를 지나쳐야 된다. 

백준에 소개된 힌트의 그림을 보자. 2-5 대각선이 존재한다. 그리고 (1,6)과 (3,4)는 그 대각선으로 분리되는 서로 반대편에 있다. 따라서 1또는 6에서 3또는 4로 넘어가기 위해서는 2또는 5를 거쳐야 한다는 것이다.

이러한 성질을 이용해 풀이를 발전시키면 한 대각선을 잡고 그 양끝점에서 각각 bfs를 하여 그 두 점으로 부터 모든 점의 거리를 알게 되면 그 대각선을 기준으로 서로 반대편에 있는 모든 쿼리에 대한 답을 할 수 있다는 것을 알 수 있게 되었다.

이 한번의 과정에서 시간의 복잡도는 간선의 개수만큼 걸릴 것이다. 이 과정을 가장 먼 두 점을 잇는 대각선으로 나누면서 반복한다. 가장 먼 두 점을 잇는 대각선을 잡은 뒤, 위의 과정을 하고, 그 대각선으로 다각형을 더 작은 두 개의 다각형으로 자른뒤에 과정을 반복하면 된다. 

나는 가장 긴 대각선이 도형의 정확히 절반을 자를 것이라고 생각했지만, 그렇지는 않았고 2개의 대각선으로 3분할은 가능했다. 분할정복을 생각한다면 총 시간복잡도 $O(MlgN)$에 문제를 해결할 수 있다.

풀이 정리

1. 다각형에서 가장 멀리 떨어진 두 점을 잇는 대각선을 찾는다. 
2. 1에서 찾은 다각형의 양쪽 끝에서 각각 bfs 를 실행하여 두 점 각각에서의 거리를 다각형의 모든 점에 대해서 구한다.
3. 대각선을 기준으로 반대편에 두 점이 있는 쿼리들에 대해서 2의 결과를 이용하여 답을 구한다.
4. 대각선을 기준으로 다각형을 자르고, 잘린 두 다각형에 대해서 1~3의 과정을 재귀적으로 반복한다.

이때, 시간복잡도를 충족하기 위해서, 재귀 과정에서 어떠한 정보들을 모두 넘겨주어야 하는지 정확하게 파악해야 한다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second 
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
 
vector<ll> v[101010];    //모든 선분
pii qry[101010]; //쿼리 모음
ll ans[101010];  //답 저장
ll acnt; //몇번째 재귀를 돌고 있는지
ll gp[101010]; //어떤 다각형 그룹에 속해있는지
ll num[101010]; // 그 그룹에서 몇번째 수인지
ll n,m; 
ll vis[101010]; //bfs tool
ll dis[101010]; // bfs2 tool
ll dis2[101010]; // bfs2 tool2
 
inline void sol(vector<ll> lis,vector<ll> qr,vector<pii> crs,vector<pii> smv){  //다각형 점 리스트
    ll i,j,k,l;
    acnt++; //재귀 횟수 늘려주고
    ll cnt=0;
    ll sz=lis.size(); //이번 다각형 점 개수
    for(auto k:lis){
        gp[k]=acnt; //이번 다각형에 속한 점들 판별
        cnt++; 
        num[k]=cnt; // 그 중에서 몇번째 점
        vis[k]=0; //초기화
        dis[k]=0;
        dis2[k]=0;
        v[k].clear();
    }
 
    if(sz<=3){ //삼각형 이하면
        for(auto k:qr) //모든 쿼리 답은 1
            ans[k]=1; 
        return;
    }
 
    for(auto p:smv){
        v[p.ff].pb(p.ss);
        v[p.ss].pb(p.ff);
    }
 
    ll x=0,y=0,mx=0;
    for(auto p:crs){
        ll i=p.ff;
        ll k=p.ss;
        ll val=min((num[i]-num[k]+sz)%sz,(num[k]-num[i]+sz)%sz); // 짧은쪽 거리재기
        if(mx<val){ // 가장 멀리 있는거 저장
            mx=val;
            x=i;
            y=k;
        }
    }
    if(x+y==0) return;
    if(x>y) swap(x,y); 
 
    queue<ll> q; //x기준 dfs
    q.push(x);
    vis[x]=1;
    while(q.size()){
        ll x=q.front(); q.pop();
        for(auto k:v[x]){
            if(gp[k]==acnt&&vis[k]==0){
                vis[k]=1;
                dis[k]=dis[x]+1;
                q.push(k);
            }
        }
    }
 
    for(auto k:lis)
        vis[k]=0;
    
    q.push(y); //y기준 dfs
    vis[y]=1;
    while(q.size()){
        ll x=q.front(); q.pop();
        for(auto k:v[x]){
            if(gp[k]==acnt&&vis[k]==0){
                vis[k]=1;
                dis2[k]=dis2[x]+1;
                q.push(k);
            }
        }
    }
 
    vector<ll> lis1(0);
    vector<ll> lis2(0);
    vector<ll> qr1(0);
    vector<ll> qr2(0);
    vector<pii> crs1(0);
    vector<pii> crs2(0);
    vector<pii> smv1(0);
    vector<pii> smv2(0);
    for(auto k:lis){ //모든 점을 두 그룹으로 분리
        if(k<=x||k>=y){
            lis1.pb(k);
            vis[k]=1;
        } 
        if(x<=k&&k<=y){
            lis2.pb(k);
            vis[k]=2;
        }
    }
    for(auto k:qr){ // 가능 쿼리에 대해서
        ll a=qry[k].ff;
        ll b=qry[k].ss;
        if(a==x||a==y||b==x||b==y||vis[a]+vis[b]==3)//다른 그룹이면 답하기
            ans[k]=min({dis[a]+dis[b],dis2[a]+dis2[b],dis[a]+1+dis2[b],dis2[a]+1+dis[b]});
        else if(vis[a]+vis[b]==2) qr1.pb(k);
        else qr2.pb(k);
    }
 
    for(auto p:crs){
        ll a=p.ff;
        ll b=p.ss;
        vis[x]=1;
        vis[y]=1;
        if(vis[a]+vis[b]==2) crs1.pb(p);
        vis[x]=2;
        vis[y]=2;
        if(vis[a]+vis[b]==4) crs2.pb(p);
    }
 
    for(auto p:smv){
        ll a=p.ff;
        ll b=p.ss;
        vis[x]=1;
        vis[y]=1;
        if(vis[a]+vis[b]==2) smv1.pb(p);
        vis[x]=2;
        vis[y]=2;
        if(vis[a]+vis[b]==4) smv2.pb(p);
    }
 
    sol(lis1,qr1,crs1,smv1);
    sol(lis2,qr2,crs2,smv2);
}
 
int main(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l;
    cin>>n;
    vector<pii> smv(0);
    for(i=1;i<n;i++){
        smv.pb({i,i+1});
    }
    smv.pb({1,n});
    v[1].pb(n);
    v[n].pb(1);
    vector<pii> crs(0);
    for(i=1;i<=n-3;i++){
        ll a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
        crs.pb({a,b});
        smv.pb({a,b});
    }
    cin>>m;
    for(i=1;i<=m;i++)
        cin>>qry[i].ff>>qry[i].ss;
    
    vector<ll> lis(0);
    for(i=1;i<=n;i++)
        lis.pb(i);
    vector<ll> qr;
    for(i=1;i<=m;i++)
        qr.pb(i);
    sol(lis,qr,crs,smv);
 
    for(i=1;i<=m;i++){
        if(qry[i].ff==qry[i].ss) ans[i]=0;
        cout<<ans[i]<<'\n';
    }
}