[KOI] 백준 10165 - 버스 노선

www.acmicpc.net/problem/10165

 

 

한 노선에 완전히 포함되는 노선은 제외하므로 솔루션은 구간을 검사하는 스위핑에 근간을 두고 있다.

 

버스 정류장이 원형으로 연결되어 있으므로 각 케이스에 대한 전략과 그 구현이 복잡해진다.

 

Step 1.

문제 접근을 용이하게 하기 위해 각 버스 노선을 두 종류로 분리해보자.

 

1. 0 을 중간점으로 경유하지 않는 노선 line

2. 0 을 중간점으로 경유하는 노선 circle

 

 

1번의 경우 버스 노선이 직선으로 생겼다고 취급해도 된다.

2번의 경우 버스 노선이 N - 1이하의 시작점에서 0번 정류소를 지나가는 형태이다.

 

Step 2.

이 두 종류의 노선에서 3가지의 경우의 수를 통해 어떤 것을 구해야 하는지 파악해보자.

 

1. line과 line의 비교

line 과 line의 비교는 단순한 스위핑을 수행하면 된다. 노선 a와 노선 b가 있을 때

$ (a.start \leq b.start) \wedge (b.end \leq a.end) $ 이면 노선 b는 a에 포함되므로 b를 배제시키면 되겠다.

 

2. circle과 circle의 비교

ciecle과 circle은 0을 기준으로 두 부분으로 나눠 각 부분을 확인할 수도 있지만 전처리를 통해 1번처럼 처리할 수 있다.

 

바로 끝나는 지점에 N만큼 더해 길이가 2N인 직선 노선으로 변환하게 되면 1번처럼 스위핑을 수행할 수 있다.

 

이렇게 해줘도 결과적으로 노선의 길이는 같음을 직접 계산해보면서 알 수 있다.

 

예제 입력에 있는 5 0과 9 4를 예로 들면

N인 10씩 더했을 때 5 10 과 9 14가 되므로 이를 비교했을 때 둘 중 하나가 나머지를 포함하지 않으므로 어느 것 하나 철거하지 않아도 된다. (당장 이 두개만 놓고 본다면)

 

여기서 5 8 이 추가된다고 해보자. 그러면 5 8은 5 10에 포함되므로 5 8은 배제된다.

 

3. line과 circle의 비교

line은 0이상에만 노선이 있고 circle은 0이전에 노선이 존재함을 유의하자.

 

즉 우리가 고려해야 할 것은 line의 종착점이 circle의 종착점보다 작거나 같은지 확인하기만 하면 된다. 만약 그렇다면 해당 line이 circle에 포함된다는 사실을 직관적으로 알아챌 수 있다.

 

그렇다면 circle의 종착점 어떤 것을 기준으로 잡아야 할까? circle의 종착점 중 가장 긴 것으로 설정하기만 하면 된다.

 

그 어떤 line도 가장 멀리 있는 종착점을 가진 circle을 넘지 못하면 바로 포함되는 것이기 때문이다!

 

 

이렇게 3가지 케이스에 대해 스위핑을 수행하면 시간 복잡도 $O(MlgM)$으로 답을 구할 수 있다.

 

구현

솔루션은 이해하기 어렵지는 않다. 하지만 그 구현이 복잡하기에 잘 풀지 못하겠다면 AC를 받은 코드를 보는 것이 도움이 될 것이다.

 

for문을 통해 데이터를 입력받으면서 circle 종착점의 최댓값 circlemax를 찾고 전처리를 하도록 한다.

 

노선에 대한 정렬은 시작점 오름차순, 종착점 내림차순으로 정렬한다.

 

그 이유는 정렬되었을 때를 기준 i + 1번째 노선이 i번째 노선에 포함되는지 선형적으로 검사할 수 있기 때문이다.

 

정렬 후 $O(n)$스위핑을 수행한다. 노선이 line일 때 circlemax 범위에 포함되는지 그 외 마지막으로 통과한 노선에 포함되는지 스위핑을 통해 답을 추려낸다.

전체 코드 : 주석을 달았다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> res;

// 노선 정렬 비교 함수
bool cmp(vector<int> &l, vector<int> &r)
{
    if (l[0] == r[0])
        return l[1] > r[1];
    return l[0] < r[0];
}

// 작은 번호부터 출력하기 위한 정렬 비교 함수
bool cmpnum(vector<int> &l, vector<int> &r) { return l[2] < r[2]; }

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> v(m, vector<int>(3));
    
    int circlemax = 0;
    
    for (int i = 0; i < m; ++i)
    {
        cin >> v[i][0] >> v[i][1];
        
        // 노선의 종류가 circle이라면
        if (v[i][0] > v[i][1])
        {
            // circle이 가질 수 있는 종착점의 최댓값을 찾는다.
            circlemax = max(circlemax, v[i][1]);
            // 스위핑 전처리를 위해 n을 더해준다.
            v[i][1] += n;
        }
        
        v[i][2] = i + 1;
    }
    
    sort(v.begin(), v.end(), cmp);
    
    vector<vector<int>> res;
    
    for (int j = 0; j < m; ++j)
    {
        // 3번 경우에 대해 검사하는 조건문이다. (line과 circle)
        // 해당 노선이 circlemax 범위 안에 포함되는가? 그렇다면 답이 될 수 없다.
        // circle의 경우는 이미 n을 더했으므로 이 조건문에 걸리지 않는다.
        if (v[j][1] <= circlemax)
            continue;

        // 어떤 노선에 포함되지 않는가?
        // 시작점은 오름차순 정렬된 상태이므로 비교하지 않아도 된다. 종착점만 비교하여 걸러낸다.
        if (res.empty() || (res.size() && res.back()[1] < v[j][1]))
            res.push_back(v[j]);
    }
    
    sort(res.begin(), res.end(), cmpnum);
    
    for (auto &t : res)
        cout << t[2] << ' ';
}