[BOJ 17619] 개구리 점프

문제

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

통나무 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이다.

예를 들어 다음과 같은 입력이 주어졌다고 해보자.

4 2
1 5 2
3 7 4
7 9 1
10 13 4
1 3
1 4

통나무의 개수 N=4이며 질문의 개수 Q=2이고, 통나무의 위치(x1~x2, y)는 (1~5, 2), (3~7, 4), (7~9, 1), (10~13, 4)이다. 주어진 질문은 1번 통나무에서 3번 통나무로 이동이 가능한지, 1번 통나무에서 4번 통나무로 이동이 가능한 지에 대한 결과를 출력으로 요구한다.

서브태스크

풀이과정

첫 번째 아이디어 (19점)

https://github.com/meraki6512/Algorithm/blob/master/AlgorithmProject1/BOJ17619_0.cpp

N개의 통나무에 대해서 parent 배열을 인덱스 i로 초기화해주고, 입력받은 x1과 x2와 i를 튜플로 만들어 벡터 v에 넣어준다.

for (i=0; i<N; i++){
    parent[i] = i;
    cin >> a >> b >> c;
    v.push_back({a,b,i});
}

N개의 통나무에 대해서 x1을 기준으로 정렬한 후, 직전 통나무와 겹쳐있는 부분이 있다면 수직 이동이 가능하므로 그래프에 연결한다. 개구리의 이동은 다른 통나무 위를 지나면 안되며 N개의 통나무를 x좌표를 기준으로 정렬했기 때문에 직전 통나무만 확인하면 된다.

//정렬
bool Compare(Tuple t1, Tuple t2){
    int x1 = get<0>(t1);
    int x2 = get<0>(t2);
    return (x1 <= x2);
}
sort(v.begin(), v.end(), Compare);

//그래프 생성
for (i=0; i<N-1; i++){
    if (isOverlapped(i, i+1)){
        Union(parent, i, i+1);
    }
}

이때, 겹쳐있다는 것은 x축 방향만을 고려한다. 예를 들어 통나무 A와 통나무 B의 위치가 각각 (1,5,2)와 (3,7,4)라면 통나무 A는 x축 방향으로 1부터 5까지 존재하고 통나무 B는 3부터 7까지 존재하므로 통나무 A와 B는 겹쳐있다. 다시 생각해보니 이 부분에서 문제가 발생한 것 같다. 즉, isOverlapped() 함수에서 바로 직전 통나무만 비교하는 것이 문제다. 통나무가 다른 통나무에 포함될 경우를 추가로 구현하면 해결될 것 같다. 이 부분만 수정해 다시 한 번 문제를 풀어볼 필요가 있다.

bool isOverlapped(int a, int b){
    int x2 = get<1>(v[a]);
    int x1 = get<0>(v[b]);
    return (x2>=x1);
}

또한, 그래프에 연결할 때는 더 작은 값을 가지는 부모로 연결시킨다.

void Union(int parent[], int a, int b){
    int x = GetParent(parent, a);
    int y = GetParent(parent, b);
    if (x<y) parent[y] = x;
    else if(x>y) parent[x] = y;
}

GetParent() 함수는 parent 배열의 값이 주어진 x값과 같아질 때까지 재귀적으로 부모를 찾아 저장하고 리턴한다.

int GetParent(int parent[], int x){
    if (parent[x]==x) return x;
    else return parent[x] = GetParent(parent, parent[x]);
}

이렇게 주어진 통나무 정보를 통해 그래프를 완성한 후에는 입력받은 질문들의 통나무가 연결되어있는지 판단한다.

bool SameParent(int parent[], int a, int b){
    int x = GetParent(parent, a);
    int y = GetParent(parent, b);
    return (x==y);
}
for (i=0; i<Q; i++){
    cin >> x >> y;
    q.push_back({GetPos(x-1), GetPos(y-1)});	//(*)
}
for (i=0; i<Q; i++){
    cout << SameParent(parent, q[i].first, q[i].second) << endl;
}

위의 코드에서 (*) 부분을 q.push_back({x-1, y-1});으로 작성해도 BOJ 채점 결과는 서브태스크 1번 통과로 동일하다. 왜 그런지는 조금 더 공부해봐야할 것 같다. 아님 무조건 순차적으로 입력되나..?

GetPos() 함수는 주어진 번호에 해당하는 통나무의 정렬된 번호를 리턴한다.

int GetPos(int x){
    for (int j = 0; j<N; j++){
        if (get<2>(v[j]) == x) {
            return j;
        }
    }
}

두 번째 아이디어 (50점, 100점)

https://github.com/meraki6512/Algorithm/blob/master/AlgorithmProject1/BOJ17619_1.cpp

첫 번째 아이디어에서는 Union-Find를 사용해 문제를 해결하였다. 아래의 코드는 N개의 통나무에 대해 그래프를 생성하는 대신 group id를 부여해 g[]라는 배열에 저장해두고, 판단 시에 배열의 값을 비교한다.

N개의 통나무에 대해서 입력받은 x1과 x2와 i를 튜플로 만들어 벡터 v에 넣어주고, Q개의 질문에 대해 입력받은 번호 a와 b를 페어로 만들어 벡터 q에 넣어준 후, v를 정렬한다. (정렬에 사용된 Compare() 함수는 1번에서 사용한 것과 동일하다.) 이때, 1번과 달리 (*)에서 GetPos() 함수를 사용하지 않았는데, 이는 후에 배열 g를 업데이트할 때 i번째가 아닌 get<2>(v[i])번째에 접근하기 때문이다.

    for (i=0; i<N; i++){
        cin >> a >> b >> c;
        v.push_back({a,b,i});
    }
    for (i=0; i<Q; i++){
        cin >> a >> b;
        q.push_back({a-1, b-1});	//(*)
    }
    sort(v.begin(), v.end(), Compare);

N개의 통나무에 대해 통나무의 x좌표에 따라서 배열 g를 저장하는데 통나무가 어떻게 위치하는지에 따라 그 방법은 다르다.

• 통나무가 직전 통나무와 겹쳐있는 경우, x2를 업데이트 해주고 직전과 동일한 gid를 배열에 저장한다.
• 통나무가 직전 통나무에 포함된 경우, 직전과 동일한 gid를 배열에 저장한다. 이때 포함된다는 것은 x1이 더 크면서 동시에 x2가 더 작은 것을 의미한다.
• 통나무가 직전 통나무와 겹쳐있지도 않은 경우, x2를 업데이트해주고, gid를 increment하여 배열에 저장한다.

x2 = get<1>(v[0]);
for (i = 1; i<N; i++){
    x1 = get<0>(v[i]);
    if (x1<=x2){
        tmp = get<1>(v[i]);
        if (tmp>x2){			//겹쳐있는 경우만
            x2 = tmp;			//비교 대상 변경
        }
    }
    else{
        gid++;
        x2 = get<1>(v[i]);
    }
    g[get<2>(v[i])] = gid;
}

예를 들어 입력의 일부가 <그림 2>와 같다고 해보자.

우선, 통나무 a의 gid는 0이고 x2는 8이다. 통나무 b를 기준으로 x1은 5고 tmp는 12인데, b는 a와 겹쳐있으므로 x2는 12로 업데이트되고 gid는 그대로 0이다. 이어서 통나무 c를 기준으로 하면 x1은 7이고 tmp는 10인데, c는 b에 포함되므로 x2는 그대로 12이고 gid도 그대로 0이다. 같은 방법으로 통나무 d를 기준으로하면 x2는 14이고 gid는 0이다. 통나무 e의 경우는 d와 겹쳐있지도 않기 때문에 x2는 17이고 gid는 1이 된다. 마찬가지로 주어진 통나무의 위치 정보를 통해 전체 통나무에 대해 gid를 부여한다.

이렇게 주어진 통나무 정보를 통해 배열을 완성한 후에는 입력받은 질문들의 통나무가 연결되어있는지 배열의 값 비교를 통해 판단한다.

for (i=0; i<Q; i++){
    x1 = q[i].first;
    x2 = q[i].second;
    cout << (g[x1] == g[x2]) << endl;
}

두 번째 아이디어에서 서브태스크 3번이 시간초과가 발생해 50점을 받았었는데, 이는 cin/cout과 scanf/printf의 속도 차이 때문에 발생한 것이었다. cin/cout이 scanf/printf에 비해 2배 이상의 속도 차이가 발생하여, N의 개수가 커졌을 때 시간 초과가 발생할 수 있음을 주의해야한다.

최종코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;
int N, Q;
int i;
typedef tuple <int, int, int> Tuple;
vector <Tuple> v;

int main(void){
    
    //초기화
    scanf("%d %d", &N, &Q);    //cin은 속도가 굉장히 느려요,,,,~
    int a, b, c;
    vector <pair<int, int>> q;
    vector <int> g(N);
    for (i=0; i<N; i++){
         scanf("%d %d %d", &a, &b, &c);    //cin은 속도가 굉장히 느려요,,,,~
        v.push_back({a,b,i});
    }
    for (i=0; i<Q; i++){
        scanf("%d %d", &a, &b);    //cin은 속도가 굉장히 느려요,,,,~       
        q.push_back({a-1, b-1});
        /*//q.push_back({GetPos(a-1), GetPos(b-1)});
        이 방법으로는 이렇게 안하는 이유:
        후에 배열 업데이트할 때, g[i]가 아닌 g[get<2>(v[i])]에 접근하기 때문이다.
        */
    }
    
    //정렬과 그룹핑
    sort(v.begin(), v.end());
    /*
    (x축 방향 기준) i번째 통나무가 i-1번째 통나무를 포함하는 경우를
    생각해봐야한다. 단순히 겹치는 경우라면 상관 없지만 포함한다면
    비교대상이 바뀌면 안되므로 x2를 업데이트 하는 일은 없어야 한다.
    */
    int gid = 0, x1, x2, tmp;
    x2 = get<1>(v[0]);
    for (i = 1; i<N; i++){
        x1 = get<0>(v[i]);
        if (x1<=x2){
            tmp = get<1>(v[i]);
            if (tmp>x2){
                x2 = tmp;
            }
        }
        else{
            gid++;
            x2 = get<1>(v[i]);
        }
        g[get<2>(v[i])] = gid;   
    }
    
    //판단
    for (i=0; i<Q; i++){
        x1 = q[i].first;
        x2 = q[i].second;
        printf("%d\n", (g[x1] == g[x2]));        //cout은 속도가 굉장히 느려요~
    }
    
    return 0;
}