[BOJ] 17619 - 개구리 점프

https://www.acmicpc.net/problem/17619

 

BOJ - 개구리 점프

문제 유형: 분리 집합, 유니온 파인드, 정렬

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 512MB

 

문제

통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다.

예를 들어 <그림 1>에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.)

 

통나무들의 위치를 입력받아 질문으로 주어진 통나무들의 쌍에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한지 판단하는 프로그램을 작성하라.

 

입력

첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 좌표는 0이상 109이하이다. 통나무들은 주어진 순서대로 1번부터 번호가 붙어 있다. 서로 다른 두 통나무는 (끝점에서도) 만나지 않는다. 다음 Q개의 줄에 서로 다른 두 통나무의 번호가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)

 

출력

Q개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 질문에 주어진 두 통나무에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한 경우 대답은 1, 그렇지 않은 경우 대답은 0이다.

 

풀이

{시작x, 끝x, 통나무번호}로 해서 배열에 넣고 정렬한다.

슬라이딩 윈도우로 밀면서 같은 그룹이 될 수 있다면, 즉 지금 그룹의 오른쪽 범위가 다음 통나무의 왼쪽 범위 이상이라면, 계속 오른쪽 범위를 확장해나가면서 분리집합을 확장해나간다.

 

최종적으로, 각 쿼리에 대해서 같은 집합에 있는지 여부를 알아내서 편하게 출력할 수 있다.

 

문제에서 y는 상관없고, 중간에 통나무가 있던말던 같은 그룹에 넣을 수 있다. 점프를 몇 번이고 할 수 있다고 했으니, 중간에 통나무가 있던 아니던 중요하지 않다. 사이에 있으면 그 만큼 더 점프해서 이동할 수 있기 때문이다.

 

코드

C++

#include <bits/stdc++.h>
#define tiii tuple<int, int, int>
using namespace std;

int getRoot(int x, vector<int>& parent) {
    if (parent[x] == -1) {
        return x;
    }
    return parent[x] = getRoot(parent[x], parent);
}

void merge(int x, int y, vector<int>& parent) {
    int rootX = getRoot(x, parent);
    int rootY = getRoot(y, parent);

    if (rootX == rootY) return;
    if (rootX < rootY) {
        parent[rootY] = rootX;
    } else {
        parent[rootX] = rootY;
    }
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> parent(n + 1, -1);
    vector<tiii> logs;
    for (int i = 1; i <= n; i++) {
        int x1, x2, y;
        cin >> x1 >> x2 >> y;
        logs.push_back(make_tuple(x1, x2, i));
    }
    sort(logs.begin(), logs.end());

    for (int i = 0; i < n; i++) {
        int j = i + 1;
        int right = get<1>(logs[i]);
        while (j < n && right >= get<0>(logs[j])) {
            right = max(right, get<1>(logs[j]));
            merge(get<2>(logs[i]), get<2>(logs[j]), parent);
            j++;
        }
        i = j - 1;
    }

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        if (getRoot(a, parent) == getRoot(b, parent)) {
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }
    return 0;
}