[백준/BOJ] 10165 버스 노선

문제 : 10165 버스노선

10165번: 버스 노선

원형으로 이루어진 버스 노선들 중에서

다른 노선에 포함되어있는 노선들을 제거한 후 출력하는 문제이다.

 

일단 원형노선을 알아보기 쉽게 일자로 펴기 위해서

0을 지나는 노선 들 중 가장 출발점이 앞선 것 기준으로 다시 정렬을 해주고

출발점 기준으로 찾으면서 도착점이 현재 최대 도착점보다 짧은 노선들을 제거 한 후

노선들을 정렬해 출력해주면 된다. 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll> pll;
struct ABC{
    ll st, ed, idx;
    ABC() {}
    ABC(ll st, ll ed, ll idx) : st(st), ed(ed), idx(idx) {}
};
bool cmp(ABC x, ABC y){
    if (x.st!=y.st)
        return x.st<y.st;
    return x.ed>y.ed;
}
ll N, M, mn=1e9+7, mx=-1;
vector<ABC> arr;
vector<ll> ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<M;i++){
        ll a, b;
        cin >> a >> b;
        arr.push_back({a,b,i+1});
        if (a>b)
            mn=min(mn,a); // 0을 지나는 노선중 가장 출발점이 앞인것 체크
    }
    if (mn==1e9+7)
        mn=0; // 그런 노선이 없었을 경우
    for (int i=0;i<M;i++){
        if (arr[i].st<mn){ // 0을 지나진 않지만 바꾼 시작지점을 지나는 경우
            arr[i].ed+=N;
            arr[i].st+=N;
        }
        else{
            if (arr[i].st>=arr[i].ed) // 0을 지나는 경우 노선의 도착지점에 N 더하기
               arr[i].ed+=N;
        }
    }
    sort(arr.begin(),arr.end(),cmp);
    for (auto x:arr){
        if (x.ed>mx){
            ans.push_back(x.idx);
            mx=x.ed;
        }
    }
    sort(ans.begin(),ans.end());
    for (auto i:ans)
        cout << i << " ";
    return 0;
}