17619 개구리 점프

Link

---

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

Detail

---

여러개의 가로 통나무를 왔다갔다 하면서, a번 통나무와 b번 통나무 사이를 도달 할 수 있는 지 묻는 문제이다.

문제의 형태가 여러개의 수직선이 놓여있고, 이들이 y값에 관계없을 때 연결되는지를 판단하는 문제였기에 자연스럽게 스위핑을 떠올리게 되었다.

내 관점에서 스위핑은 여러개의 수직선을 하나로 통합하는 행위라고 느끼게 되어서, 해당 알고리즘을 바로 적용했다.

스위핑을 위해서 시작점 정렬을 할 경우 기존 통나무의 번호를 잃어버린다는 점을 알아내지 못해서 두번의 WA를 받았지만, 해당 부분 해결 후에 AC를 받아냈다.

Code

---

#include <bits/stdc++.h>  
  
using namespace std;  
  
int main() {  
    // fast io  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
  
    int woods_cnt;  
    int q_cnt;  
  
    cin >> woods_cnt >> q_cnt;  
  
    vector<tuple<int, int, int>> woods(woods_cnt);  
    vector<int> group(woods_cnt); // group[i] = i번째 나무가 속한 그룹 번호  
  
    int x1, x2, y;  
    for(int i = 0; i < woods_cnt; i++) {  
       cin >> x1 >> x2;  
       woods[i] = {x1, x2, i};  
       cin >> y; // y는 입력받고 버림. 스위핑 해버릴꺼라서  
    }  
  
    sort(woods.begin(), woods.end());  
    int group_num = 0, last_position = -1;  
    for(int i = 0; i < woods_cnt; i++) {  
       auto [left, right, idx] = woods[i];  
  
       // 끊어져있다면 다음 그룹으로 그룹 증가  
       if(left > last_position) {  
          group_num++;  
       }  
       group[idx] = group_num;  
       last_position = max(last_position, right);  
    }  
  
    for(int i = 0; i < q_cnt; i++) {  
       int a, b;  
       cin >> a >> b;  
  
       cout << ((group[a - 1] == group[b - 1]) ? 1 : 0) << '\n';  
    }  
}