[BOJ] 백준 17619 개구리 점프

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

Approach

합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

통나무 A에서 통나무 B로 갈 수 있다는 것은 두 통나무의 X좌표 구간이 교집합(겹치는 구간)을 가집니다.

즉, Y좌표는 정답을 구하는데 아무런 영향을 미치지 않는다.

만약, A와 B 두 통나무 사이에 다른 통나무들이 존재한다면 그 통나무들을 거쳐서 가면 된다.

ex) {A} - {다른 통나무} - {B} 순차적으로 건너 A에서 B로 도달할 수 있습니다.

1. 먼저 모든 통나무를 시작 X좌표 순으로 정렬한다.

2. 정렬된 배열 상에서 인접한 두 통나무의 X좌표가 교집합을 가진다면

   두 통나무는 같은 그룹으로 분류하고 그렇지 않다면 새로운 그룹으로 분류하는 과정을 반복하면 된다.

3. 위와 같은 과정을 거쳐 질문으로 주어지는 두 통나무가 같은 그룹으로 분류되었다면

   이동이 가능하므로 1을, 그렇지 않다면 이동이 불가능하므로 0을 출력한다.

 

시뮬레이션

먼저 통나무를 X 좌표 순으로 정렬한다.

그룹 번호는 1부터 시작한다고 하자. 통나무1은 그룹1에 속한다.

이후 인접한 두 통나무를 비교한다.

통나무1과 통나무2는 X = 3~6사이의 교집합을 가지고 있으므로

통나무2는 그룹1에 속한다. 통나무2와 통나무3은 X = 7의 교집합을 가지고 있으므로 통나무3 역시 그룹1이다.

통나무4는 인접한 통나무3과 아무런 교집합이 없다. 이 경우 새로운 그룹으로 간주, 그룹2에 속한다.

▶ [질문1] 통나무1 → 통나무3 ? 그룹1로 같은 그룹이므로 "1" 출력

▶ [질문2] 통나무1 → 통나무4 ? 각각 그룹1, 그룹2로 다른 그룹이므로 "0" 출력

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 100001;
struct Trunk{
    int sx, ex, num;
    bool operator<(const Trunk &r) const {
        if (sx != r.sx) return sx < r.sx;
        return ex < r.ex;
    }
} trunks[LM], trr[LM];
int quest[LM][3], group[LM] = { 0 }, N, query;
 
void mergeSort(Trunk *arr, int s, int e) {
    if (s >= e)
        return;
    // 1. divide
    int m = (s + e) / 2;
    // 2. conquer
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
    // 3. merge
    int i = s, j = m + 1, k;
    for (k = s; k <= e; ++k) {
        if (i > m) trr[k] = arr[j++];
        else if (j > e) trr[k] = arr[i++];
        else if (arr[i] < arr[j]) trr[k] = arr[i++];
        else trr[k] = arr[j++];
    }
    // 4. copy
    for (i = s; i <= e; ++i) {
        arr[i] = trr[i];
    }
}
 
void frogJump(){
    int i, groupNumber = 1, pivot;
    group[trunks[0].num] = groupNumber;
    pivot = trunks[0].ex;
    // 통나무 그룹화
    for (i = 1; i < N; i++){
        // 겹치는 구간이 생긴 경우
        if (pivot >= trunks[i].sx){
            // 다음 통나무의 끝점이 현재 pivot보다 크면 갱신
            if (pivot < trunks[i].ex) pivot = trunks[i].ex;
        }
        // 겹치지 않는다면 새로운 그룹을 형성하고
        // 해당 통나무의 끝점을 새로운 기준으로 설정
        else{
            groupNumber++;
            pivot = trunks[i].ex;
        }
        group[trunks[i].num] = groupNumber;
    }
    for (i = 0; i < query; i++) {
        // 같은 그룹의 통나무인 경우
        if (group[quest[i][0]] == group[quest[i][1]])
            printf("1\n");
        else
            printf("0\n");
    }
}
 
int main(){
    int i, sx, ex, y;
    scanf("%d %d", &N, &query);
    for (i = 0; i < N; i++){
        scanf("%d %d %d", &trunks[i].sx, &trunks[i].ex, &y);
        trunks[i].num = i + 1; // 통나무 번호(1 ~ N)
    }
    // x좌표 기준 정렬
    mergeSort(trunks, 0, N-1);
    for (i = 0; i < query; i++){
        // quest[i][0]에서 quest[i][1]로 점프 가능 여부
        scanf("%d %d", &quest[i][0], &quest[i][1]);
    }
    frogJump();
}