BOJ 10165 - 버스 노선

www.acmicpc.net/problem/10165

10165번: 버스 노선

 

이 문제는 그리디로 풀어야 하는 문제이다.

이 문제의 가장 핵심 부분은 버스의 노선 [start, end] 가 start > end 일때 어떻게 처리하느냐 이다.

 

만약 모든 입력이 [start, end] (start < end) 이라면, 입력 값들을 정렬할때, start 가 작은 순대로 앞으로 오게 하고, start 가 만약 같은 경우라면, end 가 큰게 앞으로 오도록 정렬하면 된다.

bool comp(Pos& p1, Pos& p2) {
    if (p1.start != p2.start) return p1.start < p2.start;
    return p1.end > p2.end;
}

 

 

이렇게 정렬한 이후, 첫번째 노선은 반드시 유효한 노선이 되고 (첫번째 노선보다 시작값이 앞서는 노선이 하나도 없기 때문), 다음 노선들과 비교할때는 끝값(end) 을 비교했을때, 앞선 값보다 큰 값이어야만, 앞선 버스 노선에 포함되는 노선이 아니기 때문에, 해당 노선은 살아남는 노선이된다.

vector<Pos> bus;
vector<int> answer;
answer.push_back(bus[0].idx);
 
int temp_idx = 0;
for (int i = 1; i < bus.size(); ++i) {
    if (bus[temp_idx].end < bus[i].end) {
        answer.push_back(bus[i].idx);
        temp_idx = i;
    }
}

 

그러나 이것만으로는 [start, end] (start > end) 인 경우를 처리할 수 없다. 

이 경우는, 문제의 그림처럼 원형으로 생각하지 말고, 모든 노선이 일직선 상에 위치한다고 생각해보고,

노선할당시 [start, end] 그대로 주지말고, [start - n, end], [start, end + n] 으로 주면, 동일한 간격의 앞 뒤 부분을 만들어서 역순으로 되어있는 부분도 처리를 할 수 있게 된다.

문제의 예제로 예를들면, [5, 0], [9, 4] 가 이에 해당하므로, [5, 0] 은 [-5, 0], [5, 10] 이 들어가고, [9, 4] 는 [-1, 4], [9, 14] 가 들어간다.

그래서 이 입력의 전체 값은 [-5, 0], [-1, 4], [0, 4], [2, 6], [5, 10], [7, 9], [9, 14] 가 들어가게 된다. (정렬한 이후 결과)

 

첫번째 값 [-5, 0] 은 반드시 포함되고, (인덱스 3)

두번째 값 [-1, 4] 는 첫번째 보다 end 값이 크므로 포함되고, (인덱스 5) 

세번째 값 [0, 4] 는 두번째 보다 end 값이 같으므로 미포함되며, (인덱스 1)

네번째 값 [2, 6] 은 두번째 보다 end 값이 크므로 포함되고, (인덱스 2)

다섯번째 값 [5, 10] 은 네번째 보다 end 값이 크므로 포함되고, (인덱스 3)

여섯번째 값 [7, 9] 는 다섯번째 보다 end 값이 작으므로 미포함되며, (인덱스 4)

마지막 값 [9, 14] 는 다섯번째 보다 end 값이 크므로 포함된다 (인덱스 5)

 

여기서 살아 남은 값들에게서 중복된 인덱스를 제거하고 추려보면 결국 2, 3, 5 만 남게 된다는 것을 알게된다.

 

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef struct {
    int start;
    int end;
    int idx;
}Pos;
 
vector<Pos> bus;
 
int n, m;
 
bool comp(Pos& p1, Pos& p2) {
    if (p1.start != p2.start) return p1.start < p2.start;
    return p1.end > p2.end;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int s, e;
        cin >> s >> e;
        if (s < e) bus.push_back({s, e, i});
        else {
            bus.push_back({s - n, e, i});
            bus.push_back({s, e + n, i});
        }
    }
    
    sort(bus.begin(), bus.end(), comp);
 
    vector<int> answer;
    answer.push_back(bus[0].idx);
    
    int temp = 0;
    for (int i = 1; i < bus.size(); ++i) {
        if (bus[temp].end < bus[i].end) {
            answer.push_back(bus[i].idx);
            temp = i;
        }
    }
    
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    
    for (int i = 0; i < answer.size(); ++i) {
        cout << answer[i] << " ";
    }
    
    return 0;
}