백준 15955번 부스터

문제 링크입니다: https://www.acmicpc.net/problem/15955

카카오 코드 페스티벌 2018 예선 D번 문제였습니다.

대회 당시에는 풀지 못했지만 같은 학교 학우이신 ssangba55님(https://blog.naver.com/pasdfq/221332735719)과 대회 공식 해설(http://tech.kakao.com/2018/08/09/code-festival-2018-round-1/)을 통해 풀 수 있었습니다.

이 문제에서 핵심은 Union Find 혹은 Disjoint-Set이였습니다.

알고리즘은 아래와 같습니다.

1. 문제에서 주어진 힌트와 다르게 처음부터 부스터를 쓴 다음에 수직으로 다음 체크 포인트로 가는 것이 최적입니다.

-> 따라서 min(abs(Xu-Xv), abs(Yu-Yv))를 구해줍니다.

2. 두 점이 수직선 상에 인접한 경우에만 간선을 이어주는 것이 최적입니다.

3. 각각의 쿼리가 의미하는 바는 가중치 X 이하인 간선들만 사용해서 두 정점을 오갈 수 있는지 여부입니다.

4. 따라서, 모든 쿼리를 입력받은 뒤, y를 기준으로 정렬, x를 기준으로 정렬합니다.(즉, 2*(N-1)개의 간선을 고려해줍니다)

5. 간선들이 추가되는 상황에서 두 정점이 연결되어있는지 여부를 Union Find를 통해 확인합니다.

6. 가중치 순서대로 모든 간선과 쿼리를 보면서, 간선이 나오면 두 정점을 하나의 집합으로 합쳐주고, 쿼리가 나오면 두 정점이 같은 집합 내에 있는지를 확인하면 됩니다.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <functional>

using namespace std;

 

const int MAX = 250000 + 1;

 

int N, Q;

vector<pair<int, int>> coord;

vector<int> ySort, xSort;

priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; //{가중치, {a, b}}

int parent[MAX];

bool answer[MAX];

 

//Union Find

int find(int a)

{

        if (parent[a] < 0)

                 return a;

        return parent[a] = find(parent[a]);

}

 

void merge(int a, int b)

{

        a = find(a);

        b = find(b);

 

        if (a == b)

                 return;

 

        if (parent[a] < parent[b])

                 swap(a, b);

        parent[b] += parent[a];

        parent[a] = b;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> Q;

 

        memset(parent, -1, sizeof(parent));

        for (int i = 0; i < N; i++)

        {

                 int y, x;

                 cin >> y >> x;

                 coord.push_back({ y, x });

                 ySort.push_back(i);

                 xSort.push_back(i);

        }

 

        //ySort에 y좌표가 작은 순서대로 인덱스 저장

        sort(ySort.begin(), ySort.end(), [&](int &a, int &b) {

                 if (coord[a].first != coord[b].first)

                         return coord[a].first < coord[b].first;

                 return coord[a].second < coord[b].second;

        });

 

        //xSort에 x좌표가 작은 순서대로 인덱스 저장

        sort(xSort.begin(), xSort.end(), [&](int &a, int &b) {

                 if (coord[a].second != coord[b].second)

                         return coord[a].second < coord[b].second;

                 return coord[a].first < coord[b].first;

        });

 

        //우선순위 큐에 간선들을 {가중치, {a, b}} 형태로 집어넣는다

        for (int i = 0; i < N - 1; i++)

        {

                 int a = ySort[i], b = ySort[i + 1];

                 pq.push({ abs(coord[a].first - coord[b].first), {a, b} });

        }

        for (int i = 0; i < N - 1; i++)

        {

                 int a = xSort[i], b = xSort[i + 1];

                 pq.push({ abs(coord[a].second - coord[b].second), {a, b} });

        }

       

        //쿼리를 {{가중치, {A, B}}, 쿼리의 번호}로 저장

        //가중치의 오름차순으로 정렬

        vector<pair<pair<int, pair<int, int>>, int>> query;

        for (int i = 0; i < Q; i++)

        {

                 int a, b, c;

                 cin >> a >> b >> c;

                 query.push_back({ {c, {a - 1, b - 1}}, i });

        }

        sort(query.begin(), query.end());

 

        for (int i = 0; i < query.size(); i++)

        {

                 pair<int, pair<int, int>> temp = query[i].first;

                 int c = temp.first;

                 int a = temp.second.first;

                 int b = temp.second.second;

 

                 //큐에서 현재 가중치보다 작거나 같은 간선이 있으면

                 //꺼내서 합쳐준다

                 while (!pq.empty())

                 {

                         int curC = pq.top().first;

                         if (curC > c)

                                 break;

                         merge(pq.top().second.first, pq.top().second.second);

                         pq.pop();

                 }

                 answer[query[i].second] = (find(a) == find(b));

        }

 

        for (int i = 0; i < Q; i++)

                 if (answer[i])

                         cout << "YES\n";

                 else

                         cout << "NO\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~