BOJ 15955 부스터


사용한 알고리즘

  • Union-find, 다익스트라

알고리즘 설명

  • 접근이 정말 재미있는 문제이다.
  • 먼저, 부스터는 x축 또는 y축으로 움직여 두 지점간의 필요한 HP 양을 알 수 있다.
  • 여기서 Query로 x, y, HP 3가지 정보를 물어보는데, 이를 위에서부터 하나씩 확인하면 TIE가 나온다… ㅠ_ㅠ
  • 발상의 전환은 Query를 따로 저장하여, HP 가 작은 Query부터 확인하는 것이다.
  • 이러한 접근을 이용하면 x <= y 일때, 두 지점이 HP가 x일때 연결되어 있다면 HP가 y일때 연결되어 있다.를 이용할 수 있다.
  • 이러한 사실로 각 Query에 HP 따라 연결 가능한 지점을 힙과 Union-find를 이용하여 연결시킨다.
  • 이후 두 지점이 연결 되어 있는지 확인한다.
  • Query 정답을 모두 구한뒤, 순서의 맞게 출력한다.

풀이

// baekjoon 15955 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
const int MAX_N=250001;

struct Point {
    int x, y, idx;
    Point(){}
    Point(int x, int y, int idx):x(x), y(y), idx(idx){}
};

bool cmp_x(const Point &a, const Point &b) {
    return a.x < b.x;
}
bool cmp_y(const Point &a, const Point &b) {
    return a.y < b.y;
}

struct Quest{
    int A, B, HP, idx;
    Quest(){}
    Quest(int A, int B, int HP, int idx):A(A), B(B), HP(HP), idx(idx){}
    bool operator<(const Quest &o) {
        return HP < o.HP;
    }
};

struct Vertex{
    int dist, A, B;
    Vertex(){}
    Vertex(int d, int a, int b):dist(d), A(a), B(b){}
};

struct cmp_v {
    bool operator() (const Vertex &a, const Vertex &b){
        return a.dist > b.dist;
    }
};

int N, Q, X, Y, from, to, H, root[MAX_N];
bool ret[MAX_N];
Quest quest[MAX_N];
Point pointX[MAX_N], pointY[MAX_N];
priority_queue<Vertex, vector<Vertex>, cmp_v> pq;

int find(int x) {
    if (!root[x]) return x;
    return root[x]=find(root[x]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    root[b]=a;
}

int main() {
    scanf("%d %d", &N, &Q);

    for (int i=1; i<=N; i++) {
        scanf("%d %d", &X, &Y);
        pointX[i]=Point(X, Y, i);
        pointY[i]=Point(X, Y, i);
    }
    sort(pointX+1, pointX+N+1, cmp_x);
    sort(pointY+1, pointY+N+1, cmp_y);

    for (int i=1; i<N; i++) {
        pq.push(Vertex(pointX[i+1].x-pointX[i].x, pointX[i].idx, pointX[i+1].idx));
        pq.push(Vertex(pointY[i+1].y-pointY[i].y, pointY[i].idx, pointY[i+1].idx));
    }

    for (int i=0; i<Q; i++) {
        scanf("%d %d %d", &from, &to, &H);
        quest[i]=Quest(from, to, H, i);
    }

    sort(quest, quest+Q);

    for (int i=0; i<Q; i++) {
        while (!pq.empty() && pq.top().dist <= quest[i].HP) {
            merge(pq.top().A, pq.top().B);
            pq.pop();
        }
        ret[quest[i].idx]=find(quest[i].A)==find(quest[i].B);
    }

    for (int i=0; i<Q; i++) {
        puts(ret[i] ? "YES" : "NO");
    }

    return 0;
}



© 2020.08. by fbdp1202

Powered by theorydb