BOJ 1848 - 동굴 탐험

문제 태그 : https://www.acmicpc.net/problem/1848

다익스트라에 관해 포스팅을 하다가 백준 다익스트라 문제들을 살펴보았는데, 한 문제 시도하다가 틀린 흔적을 발견했다. 그래서 그 문제를 풀게 되었는데, 굉장히 좋다고 생각하여, 풀이도 저장할겸 포스팅을 하게 되었다.

문제 설명

양 방향 그래프가 주어지는데 일반적인 양방향 그래프와 다른 점은 A점에서 B점으로 갈 때의 비용과 B점에서 A점으로 갈 때의 비용이 다르다는 것이다. 이때 목적은 1번 정점에서 출발하여 1번 정점으로 다시 돌아오는 최단거리를 구하는 것이다. 이때 한 번 지난 간선은 역으로도 다시 올 수 없다는 것이다. 즉 다시 말해, 1->3->1의 경로로 이동하는 것은 안된다는 것이다.

문제 풀이 (사고의 흐름)

일단 사이클에서 1번 정점으로 들어오기 직전의 정점 i를 잡는다면 우리는 1-i 의 간선을 빼고 1에서 다익스트라를 돌린 후에 i까지의 거리를 구하고 i->1의 거리를 더해서 구할 수 있다. 이 아이디어는 관찰을 통해 얻어야 하며 중요하다. 하지만, 이것만으로 코딩을 하게 된다면 시간초과가 난다. 다익을 n번 돌려야 하므로 시간 복잡도는 O(NMlgM)이며 이는 옛날의 나의 코드이다. 

시간복잡도에 대한 생각을 해보았다. 다익 한 번, O(MlgM)은 되지만, N에 관련이 없기가 힘들다. 그렇다면 O(MlgMlgN)은 어떨까? N을 lgN으로 줄이는데는 두 가지를 생각해보았다. 1.세그먼트 트리 2. 분할 정복. 분할 정복이 생각난순간 풀이가 완성되었다. 

1번 정점과 연결된 정점들을 a1,a2,a3......ak 라고 하자. 이때 우리의 목표는 임의의 ai에서 aj로 가는 최단거리를 구하는 것이다. 우리는 위의 그룹을 1:(a1,a3,a5,a7...a k-1) 와 2:(a2,a4,a6,a8,.....ak)로 나눌수 있다. 이때 1번 정점에서 1번 그룹과 연결된 선분을 끊고 다익스트라를 하면 우리는 2번 그룹의 정점을 거쳐 출발해 1번 정점으로 들어가는 경우에 대해 최단 거리를 모두 알 수 있다. 이를 반대로 하면 1번 그룹의 정점을 거쳐 출발해 2번 정점으로 들어가는 경우의 최단거리도 구할 수 있다. 이제 그룹1->그룹1 & 그룹2->그룹2의 경우를 구하면 되는데 이는 다시 그룹을 반으로 나누는 과정을 통해서 구할 수 있다. 이 과정을 반복하면 다익을 상수 * lgn 번만에 임의의 ai에서 aj로 가는 최단거리를 구할 수 있다. 이때 1->ai->aj->1의 거리의 최솟값을 구하면 된다.

위에서 언급했던 것처럼 시간복잡도는 O(M lgM lgN).

 구현 방식

- 선분을 끊었다고 생각하기 위해 지우는 것은 힘들기 때문에 다익을 돌릴 때 1번 정점에서 시작하는 것이 아니라 1과 연결되었다고 생각하는 정점들을 거리와 함께 priority_queue에 넣어주고 시작을 하면 된다.
- 그룹 내부에서 다시 세부적으로 나누는 것은 귀찮기 때문에 몇 번 2개의 그룹으로 나눠 임의의 서로다른 i,j가 한 번이라도 다른 그룹에 있으면 된다.
- 이때 bit의 개념을 사용해 굉장히 간편하게 분리할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
 
vector<pii> edg[20202];
ll dis[303030];
ll inf=1e18;
 
ll in[303030];
ll out[303030];
 
vector<ll> lnk;
ll ans=1e18;
 
void dijk1(ll bit){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    for(auto x : lnk)
         if(x&(1 << bit)){
             pq.push({in[x],x});
             dis[x]=in[x];
         }
    while(!pq.empty()){
        auto x = pq.top(); pq.pop();
        if(dis[x.ss]<x.ff) continue;
        for(auto n : edg[x.ss])
            if(dis[x.ss]+n.ff<dis[n.ss]){
                dis[n.ss]=dis[x.ss]+n.ff;
                pq.push({dis[n.ss],n.ss});
            }
    }
}
 
void dijk2(ll bit){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    for(auto x : lnk)
         if( ! (x&(1 << bit))){
             pq.push({in[x],x});
             dis[x]=in[x];
         }
    
    while(!pq.empty()){
        auto x = pq.top(); pq.pop();
        if(dis[x.ss]<x.ff) continue;
        for(auto n : edg[x.ss])
            if(dis[x.ss]+n.ff<dis[n.ss]){
                dis[n.ss]=dis[x.ss]+n.ff;
                pq.push({dis[n.ss],n.ss});
            }
    }
}
 
int main(){
    ll i,j,k,l,m,n,u,v,c,d;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%lld %lld %lld %lld",&u,&v,&c,&d);
        if(u!=1&&v!=1) {
            edg[u].emplace_back(c,v);
            edg[v].emplace_back(d,u);
        }
        if(u*v==u){
            lnk.push_back(u);
            out[u]=c;
            in[u]=d;
        }
        if(v*u==v){
            lnk.push_back(v);
            out[v]=d;
            in[v]=c;
        }
    }
 
    for(i=0;i<=12;i++){
        for(j=1;j<=n;j++)
            dis[j]=inf;        
        dijk1(i);
        for(auto x:lnk)
            if( !(x&(1 << i)) ) 
                 ans=min(ans,out[x]+dis[x]);    
        for(j=1;j<=n;j++)
            dis[j]=inf;
        dijk2(i);
        for(auto x:lnk)
            if( (x&(1 << i)) ) 
                 ans=min(ans,out[x]+dis[x]);
    }
    printf("%lld",ans);
}