개구리 점프( BOJ 17619 )

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

17619번: 개구리 점프

 

문제 파악하기

개구리가 점프를 해서 원하는 통나무까지 이동할 수 있는지 확인하는 문제입니다. 통나무들은 항상 가로방향으로 연못에 떠 있으며, 개구리는 항상 수직적인 방향으로 점프할 수 있습니다. 그렇기에 개구리는 항상 통나무의 값이 조금이라도 겹친다면 무조건 점프할 수 있습니다. 따라서, 우리는 모든 통나무에 대해서 서로 겹쳐있는지 확인하고, 겹쳐진 통나무를 하나의 집합으로 묶어놓으면 됩니다.

 

문제 해결하기

그럼 통나무끼리 서로 겹쳐졌는지 확인하는 방법을 생각해봅시다. 통나무끼리 겹쳐있다는 건 y값을 제외한 x1과 x2의 값이 서로 겹쳐있다는 의미입니다. 이는 중첩 반복문을 사용하면 쉽게 구할 수 있지만, 통나무의 개수가 최대 100,000개이기 때문에 좀 더 효율적인 방법이 필요합니다. 이런 경우에는 정렬을 사용할 수 있습니다.

 

x1의 값을 기준으로 정렬한 다음, 우리는 x1의 값을 비교하면서 겹쳤는지 판단할 수 있습니다. 우선, 지금까지 겹쳐있는 통나무들의 최솟값과 최댓값을 각각 minX와 maxX라고 하겠습니다. 그리고 현재 i번째 통나무(inp[i])가 이전 통나무들과 겹쳤는지 판단하기 위해서는 maxX와 inp[i]의 x1값을 비교하면 됩니다. 만약 x1의 값이 maxX보다 작다면, i번째 통나무는 이전 통나무들과 겹치게 된다는 의미이기에 이전 통나무와 같은 집합에 넣어주고, maxX와 x2의 값을 비교해서 갱신해줍니다. 하지만 inp[i]의 x1값, 즉 i번째 통나무의 왼쪽 위치가 maxX보다 크다면 i번째 통나무는 이전 통나무들과 겹치지 않습니다. 그렇기에 새롭게 집합을 만들어주고, minX와 maxX의 값을 i번째 통나무의 값으로 갱신하면 됩니다.

 

이렇게 집합으로 분류한 다음에는 Q개의 쿼리를 처리하면 됩니다. 처리할 때에는 각각의 통나무의 집합을 확인해서 서로 같은 집합이라면 1을, 아니라면 0을 출력하면 됩니다.

 

소스코드

#include <stdio.h>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>
#define NMAX 100010
#define PAIR pair<int, int>
using namespace std;
 
struct INP {
    int x1, x2;
    int idx;
 
    bool operator== (INP p) { return x1==p.x1 and x2==p.x2; }
    bool operator< (INP p) {
        if(x1 == p.x1) return x2 < p.x2;
        else return x1 < p.x1;
    }
};
 
int N, x1, x2, y;
int Q, q1, q2;
vector< INP > inp;
 
int curMin, curMax;
int parent[NMAX];
 
int find(int p) {
    if(parent[p] == p) return p;
    else return parent[p] = find(parent[p]);
}
 
int main() {
    scanf("%d %d", &N, &Q);
    for(int i=1;i<=N;i++) {
        scanf("%d %d %d", &x1, &x2, &y);
 
        inp.push_back({x1, x2, i});
    }
 
    // 정렬(x1기준) 및 분리집합 초기화
    sort(inp.begin(), inp.end());
    for(int i=1;i<=N;i++) parent[i] = i;
 
 
    curMin = inp[0].x1;
    curMax = inp[0].x2;
    for(int i=1;i<N;i++) {
        // 선분이 이전 선분과 겹치는 경우
        if(inp[i].x1 <= curMax) {
            parent[inp[i].idx] = find(inp[i-1].idx);
            curMax = max( curMax, inp[i].x2 );
        }
        else {
            curMin = inp[i].x1;
            curMax = inp[i].x2;
        }
    }
 
    for(int i=1;i<=Q;i++) {
        scanf("%d %d", &q1, &q2);
 
        // 분리집합으로 판별
        printf("%d\n", find(q1) == find(q2));
    }
}

후기

정렬을 활용하는 분리집합 문제입니다. 선분의 겹침을 판단하는 알고리즘은 은근 많이 출제되는 유형이라는 생각이 듭니다.  다만, 이 문제는 선분의 겹침 혹은 정렬보다는 분리집합의 개념을 연습하는데 적합한 문제라고 생각합니다.