[백준] 징검다리 달리기2(1810)

문제 링크 : [백준] 징검다리 달리기2(1810)

문제 설명

(x,y) 좌표를 가지는 n개의 징검다리가 있을 때, (0,0)에서 시작하여, 현재 위치에서 x,y 좌표의 차이가 2 이내인 징검다리들만을 이동하여, y좌표가 F에 다다르는 최단 이동거리를 구하시오.

입력

n(징검다리의 갯수, 1<=n<=50,000)
F(목표 y 좌표, 0<=F<=1,000,000)
xi yi(n개의 징검다리의 x,y 좌표)

5 3
1 2
6 3
4 1
3 2
0 2   

출력

목표 지점까지의 최단거리(정수부분 반올림)

8

카테고리

#정렬, #이분탐색, #다익스트라

시간 복잡도 상한

O(nlogn)

해결 방법

1. 기본 틀은 (0,0)에서 (any,F)까지 가는 최단 거리를 다익스트라로 구하면 됩니다.
2. 노드에 대한 입력만 주어지기 때문에 노드간 엣지를 구해야합니다.
3. 입력을 받을 때, 각 y좌표 별로 x 좌표를 리스트로 연결해놓습니다.
   3-1. Visited 배열 관리를 위하여, x좌표와 노드 index를 함께 저장합니다.
4. Priority Queue에서 나오는 노드별로 일반적인 다익스트라의 형태로 도착점까지의 최단거리를 구합니다.
   4-1. y좌표의 제약(두 y좌표의 차이가 2이내)은 인접리스트 인덱스로 확인이 가능합니다.
   4-2. x좌표의 제약은 벡터의 처음부터 끝까지 탐색을 하면 가능하나, 최악의 경우, O(n2)이 됩니다.
   4-3. 따라서 y좌표별로 인접리스트를 x 좌표로 정렬을 하고, 가능한 x좌표를 lower_bound와 upper_bound를 이용하여 O(nlogn)에 구할 수 있습니다.

시간복잡도

O(nlogn)

코드

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
struct N{
    N(double c,int x,int y,int i):c(c),x(x),y(y),i(i){}
    double c;
    int x,y,i;
    bool operator<(const N&t)const{
        return c>t.c;
    }
};
int n,m,a,b,d[50001],i,p;
vector<pair<int,int>> v[1000001];
priority_queue<N>q;
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        v[b].push_back({a,i});
    }
    for(i=0;i<1000001;i++)sort(v[i].begin(),v[i].end());
    q.push({0,0,0,0});
    while(!q.empty()){
        N c=q.top();q.pop();
        if(c.y>=m){
            printf("%.0lf",round(c.c));
            return 0;
        }
        if(d[c.i])continue;
        d[c.i]=1;
        for(i=-2;i<3;i++){
            p=c.y+i;
            if(p<0||p>1000000)continue;
            vector<pair<int,int>>z=v[p];
            a=lower_bound(z.begin(),z.end(),make_pair(c.x-2,0))-z.begin();
            b=upper_bound(z.begin(),z.end(),make_pair(c.x+2,0))-z.begin();
            for(a=0;a<z.size();a++){
                if(abs(z[a].first-c.x)>2||d[z[a].second])continue;
                q.push(N(c.c+sqrt(pow(c.x-z[a].first,2)+pow(c.y-p,2)),z[a].first,p,z[a].second));
            }
        }

    }
    printf("-1");
}