버스 노선

작성일 | In

[백준] 10165번 - 버스 노선

문제 링크

순환 버스 노선들 중 다른 노선에 포함되는 노선들을 제거하여 최소한의 버스 노선만을 남겨두는 문제이다.

문제가 어렵다고 느껴진 이유는 경로가 “순환” 형태이기 때문이다. 따라서 노선 간 포함관계를 따지기 까다롭다.
이를 위해 노선을 2가지 그룹으로 구별할 필요가 있다. 시작 정류장 번호가 끝 정류장 번호보다 작은 A 그룹, 이와 반대인 B 그룹으로 노선들을 구분할 수 있다.
이렇게 그룹을 나누면 A 그룹의 노선은 B 그룹의 노선을 포함할 수 없다. 즉, 우리는 A 그룹 내의 포함관계, B 그룹 내의 포함관계, 그리고 B 그룹 노선이 A 그룹의 노선을 포함하는지, 이렇게 3가지 경우를 고려하면 된다.

포함 관계 판단 전 약간의 정렬을 수행하면 더 쉽게 판단할 수 있다. 벡터에 노선 정보를 입력을 받고난 뒤 start 가 작은 순으로, start가 같을 시 end가 큰 순으로 정렬해주면, 앞 인덱스의 노선이 뒤 인덱스의 노선에 포함되는 경우는 없게 된다. 즉, 뒤 인덱스의 노선이 자기 바로 앞 인덱스의 노선에 포함되는지만 확인하면 된다. 디테일한 판단 방법은 아래와 같다.

  1. A 그룹 내의 노선들의 포함 관계는 판단하기 쉽다. A 그룹 내에 두 노선 a,b가 있을 때, b.start <= a.start && a.end <= b.end 이면 노선 a는 b에 포함되므로 제거할 수 있다.
    (두 개 이상의 동일한 노선은 입력으로 주어지지 않으므로 이는 고려하지 않아도 된다.)
  2. B 그룹 내의 노선들의 포함 관계를 판단하기 위해선 B 그룹 내의 노선의 end에 N을 더해준 뒤, A 그룹 내 포함관계를 판단할 때와 같은 방법으로 판단하면 된다.
  3. 마지막으로, B 그룹의 노선들이 A 그룹의 노선을 포함하는지는 어떻게 판단할까? A 그룹 노선보다 B 그룹 노선의 start가 앞서있다는 사실을 이용하면, B 그룹 노선의 end가 A 그룹 노선보다 뒤에 있다면 포함관계가 성립한다. 아울러 이 작업을 모든 B 그룹 노선에 대해 수행할 필요는 없다. B 그룹 노선들 중 가장 큰 end를 기준으로 비교하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

struct bus_route {
    int s, e, num;

    bus_route(int num, int s, int e): s(s), e(e), num(num) {}

    bool operator < (struct bus_route& a) {
        if(this->s == a.s)
            return this->e > a.e;
        return this->s < a.s;
    }
};

bool comp(struct bus_route& a, struct bus_route& b) {
    return a.num < b.num;
}

vector<struct bus_route> route;
int n,m;

int main(void) {
    scanf("%d %d", &n, &m);

    int maxEnd=0; // B 그룹 중 가장 큰 end
    for(int i=1; i<=m; ++i) {
        int s,e;
        scanf("%d %d", &s, &e);
        if(s < e)
            route.push_back({i, s, e});
        else {
            maxEnd = max(maxEnd, e);
            route.push_back({i, s, e+n}); // 뒤에서 e로 포함 여부를 판단하므로 B 그룹의 노선은 e+n으로 저장
        }
    }

    sort(route.begin(), route.end()); // s 오름차순, e 내림차순으로 정렬

    deque<struct bus_route> ans;
    // A 그룹 내에서, 혹은 B 그룹 내에서 포함되는 노선 거르기
    for(int i=0; i<route.size(); ++i) {
        if(ans.empty() || route[i].e > ans.back().e)
            ans.push_back(route[i]);
    }

    // A 그룹 중 B 그룹의 노선에 포함되는 노선들 거르기
    while(!ans.empty() && ans.front().e <= maxEnd)
        ans.pop_front();

    // 노선 번호 오름차순으로 정렬
    sort(ans.begin(), ans.end(), comp);
    for(int i=0; i<ans.size(); ++i)
        printf("%d ", ans[i].num);
}
0%