[PS] 백준 15955번: 부스터

|

문제

내가 이해한 문제 내용

$N$개의 체크포인트와 $Q$개의 쿼리가 주어진다. 각 쿼리는 체크포인트 $A_i$에서 체크포인트 $B_i$로 HP 제한 $X_i$인 상태에서 이동하라고 말한다. 이 때 각 쿼리가 유효한지, 즉 이동할 수 있는지 판단하시오.

접근 방식

진짜 개어려운 문제다. 풀이를 보고 간신히 이해했고 코드 짜는데도 한참 걸렸다. 먼저 처음에 접근한 방식은 너무 단순하게 예제를 푸는 프로세스를 그대로 따라간 것 같다. 굳이 안 적어도 될 것 같다.

풀이는 블로그카카오 공식해설을 참고했다.

이 문제는 문제가 요구하는 바를 명확하게 파악하여 문제를 재정의해야 하는데 그게 굉장히 어렵다. 먼저 임의의 체크포인트에서 다른 체크포인트로 이동하는데 상당히 많은 경우의 수가 있는 것처럼 느껴지기 때문에 자명한 부분을 파악해야 한다.

  1. HP와 부스터의 충전여부를 알아야 하는가?

만약 체크포인트에서 HP 혹은 부스터를 충전하지 않고 나중에 다시 와서, 그러니까 2번째 이상의 방문에서 충전한다고 하자. 이럴 경우 처음부터 충전하고 가는 경우와 동일하기 때문에 처음부터 체크포인트에서 HP와 부스터를 충전한다고 결론 내릴 수 있다.

  1. 임의의 체크포인트에서 다른 체크포인트로 이동하는데 어떤 경로가 최적인가?

나는 처음에 이동하는 방법을 뭔가 복잡하게 생각했는데 단순하게 생각하면 되는 것이 부스터와 걷기를 사용하면 된다는 것이다.

  • 걸어서 체크포인트와 수직/수평으로 이동 + 부스터로 체크포인트로 이동
  • 부스터로 동/서/남/북 방향으로 이동 + 걸어서 체크포인트로 이동

즉, 부스터를 먼저 쓰냐 아니면 걷기를 먼저 쓰냐의 차이인데 어떤 걸 먼저 사용하든 부스터는 항상 사용하기 때문에 부스터를 항상 먼저 쓴다고 해도 상관이 없다.

항상 부스터를 먼저 사용하기 때문에 걸어가야 하는 거리가 얼마인지만 판단하면 된다. 아래 그림을 보자.

체크포인트 A(1,2)에서 체크포인트 B(3,9)로 이동할 때 두 방향 모두 처음부터 부스터를 쓰는데 거리가 더 큰 것에 부스터를 쓰는 것이 걷는 거리를 훨씬 줄여주므로 두 체크포인트 간에 사용해야 하는 HP는 $min(abs(X_a-X_b),abs(Y_a-Y_b))$라고 할 수 있다. 이렇게 각 체크포인트 사이의 가중치를 계산하면 거의 $N^2$개의 간선이 생기며 DFS를 통해 해결하게 되면 $O(QN)$의 시간이 필요하기 때문에 TLE가 발생한다.

따라서, 굉장히 중요한 관찰을 하나 해야 한다.

A에서 B로 이동할 수 있고 B에서 C로 이동할 수 있으면 A에서 C로 이동할 수 있다.

즉 위에선 모든 간선을 다 구해냈지만 그럴 필요가 없는 것이 A에서 C로 이동하는 것보다 A에서 B를 거쳐 C로 이동하는 것이 훨씬 이득이기 때문에 각 체크포인트에서 인접한 체크포인트까지의 간선만 구해주면 된다. 인접한다는 것은 X좌표 혹은 Y좌표 기준으로 인접할 수 있다는 것을 말하므로 X,Y좌표 기준으로 각각 정렬해주어야 한다.

이제 각 쿼리에 대해서 응답을 해야 하는데 각 쿼리가 말하는 바가 특정 체크포인트에서 다른 체크포인트로 주어진 HP 내에서 이동할 수 있느냐를 물어보는 것이므로 간선을 뽑아내서 해당 간선이 주어진 HP의 조건을 만족시키면 유니온-파인드로 묶어주는 것이 또 하나의 중요한 관찰이다.

주의할 점은 HP가 큰, 즉 간선의 가중치가 큰 정점끼리 유니온-파인드로 묶게 되면 나중에 HP의 조건을 만족시키는 간선이 없다 하더라도 이미 같은 집합안에 속할 수 있다는 점이다. 따라서, 가장 작은 가중치를 갖는 간선부터 체크해야 하며 그러기 위해선 쿼리를 HP 기준으로 정렬시켜야 한다. 또한 각각의 간선에 대해 작은 가중치를 갖는 것부터 뽑아내기 위해 우선순위 큐를 사용해야 한다.

우선순위 큐에서 주어진 HP의 조건을 만족시키는, 즉 HP 이하의 가중치를 갖는 간선들을 전부 뽑아내서 뽑아낼 때마다 유니온-파인드로 묶어준 후에 쿼리에서 묻는 2개의 체크포인트 같은 집합 안에 속하면 YES인 것이고 아니라면 NO인 것이다.

단, 마지막에 헤멘 부분이 쿼리를 정렬했으니 다시 처음의 인덱싱을 기반으로 출력해줘야 한다는 점이다.

어려웠던 점 & 배운 점

  • 그냥 개어려움, 정렬과 유니온-파인드 밖에 안쓰긴 하지만 문제해결기법 자체를 생각하기가 어려움
  • 문제를 그냥 나이브하게 받아들이지 말고 특정한 것을 관찰하려고 하자. 다양한 시각에서 바라보자.

시간복잡도

  • X좌표 및 Y좌표 기준 정렬 $O(NlgN)$
  • 쿼리 정렬 $O(QlgQ)$
  • 쿼리 돌면서 유니온-파인드로 묶기 $O(Q+NlgN)$
  • 최종 $O(NlgN+QlgQ)$

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

struct query{
    int from;
    int to;
    int hp;
    int idx;

    bool operator<(const query& rhs){
        return hp<rhs.hp;
    }
};

struct vertex{
    int x;
    int y;
    int idx;

    bool operator<(const vertex& rhs){
        return x<rhs.x;
    }
};

struct edge{
    int v1;
    int v2;
    int w;
};

struct Comparator {
    bool operator() (const edge& e1, const edge& e2) {
        return e1.w > e2.w;
    }
};

const int MAX_SIZE = 250005;
int n,q,cx,cy,a,b,hp;
int p[MAX_SIZE],r[MAX_SIZE],ans[MAX_SIZE];
query qu[MAX_SIZE];
vertex xv[MAX_SIZE],yv[MAX_SIZE];
priority_queue<edge,vector<edge>,Comparator> pq;

bool cmp(vertex a, vertex b) {
    return a.y==b.y?a.x<b.x:a.y<b.y;
}

int find(int v) {
    if(p[v]==v) return v;
    else return p[v]=find(p[v]);
}

void uni(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);

    if(p1==p2) return;

    if(r[p1]<r[p2]) p[p1]=p2;
    else if(r[p1]>r[p2]) p[p2]=p1;
    else {
        p[p1]=p2;
        r[p2]++;
    }
}


int main(void)
{
    scanf("%d%d",&n,&q);
    for(int i=1; i<=n; i++){
        scanf("%d%d",&cx,&cy);
        xv[i] = yv[i] = {cx,cy,i};
        p[i] = i;
        r[i] = 1;
    }

    for(int i=1; i<=q; i++){
        scanf("%d%d%d",&a,&b,&hp);
        qu[i] = {a,b,hp,i};
    }

    /*
        x좌표 및 y좌표 기준으로 정렬
        왜? 임의의 체크포인트에서 다른 체크포인트로 가는 최적의 방법이
        체크포인트와 수직/수평이 되는 방향으로 걷기 + 부스터로 체크포인트로 가기이기 때문에
        두 체크포인트 간의 가중치를 (x좌표 차이)와 (y좌표 차이)로 둘 수 있음
        O(NlgN)
    */ 

    sort(xv+1,xv+n+1);
    sort(yv+1,yv+n+1,cmp);

    /*
        x,y좌표 기준으로 정렬된 배열을 보면서
        인접한 체크포인트와 그 가중치를 "간선"으로 우선순위 큐에 삽입
        O(NlgN)
    */

    for(int i=2; i<=n; i++){
        int bxidx = xv[i-1].idx;
        int cxidx = xv[i].idx;

        int byidx = yv[i-1].idx;
        int cyidx = yv[i].idx;

        pq.push({bxidx,cxidx,xv[i].x-xv[i-1].x});
        pq.push({byidx,cyidx,yv[i].y-yv[i-1].y});
    }

    /*
        쿼리를 주어진 HP 기준으로 정렬
        왜? HP가 큰 것부터 하면 유니온-파인드로 합쳤을 때 
        HP가 작은 쿼리에 대해서 잘못된 결과가 도출될 수 있기 때문.
    */
    sort(qu+1,qu+q+1);

    for(int i=1; i<=q; i++){
        while(!pq.empty() && pq.top().w<=qu[i].hp) {
            edge e = pq.top(); pq.pop();
            uni(e.v1,e.v2);
        }
        ans[qu[i].idx] = find(qu[i].from)==find(qu[i].to) ? 1 : 0;
    }

    for(int i=1; i<=q; i++){
        ans[i] ? puts("YES") : puts("NO");
    }
    
    return 0;
}