[백준 10165] 버스 노선

그리디는 어렵다. 나는 스위핑으로 문제를 풀었지만, 그리디로 푸는 풀이도 있어 둘다 작성한다.

1. 스위핑 풀이

먼저 \(S\)는 \([0\;N−1]\) 사이의 노선, 즉 반대로 넘어가지 않는 노선이라 하고, \(T\)는 \(N−1\)을 지나가는 노선, 반대로 넘어가는 노선이라고 칭한다.

만약에 원형이 아닌 선형에 \(S\)만 있는 노선이라고 가정해보자, 노선들을 시작점으로 정렬을 하고 시작점이 같다면 끝점이 더 멀리에 있는 순으로 정렬한다. Line Sweeping을 하는데 현재 확장된 노선들에서 새로 들어온 단일 노선의 끝이 확산된 노선들의 끝보다 작다면 다른 노선에 포함되어있다고 판별하면 된다.

다시 원형으로 돌아와서, \(S,T\)가 포함관계를 가지는 가짓수에 대해 생각해볼 수 있는데, \(S−>S\), \(T−>T\), \(T−>S\) 이 \(3\)가지 경우가 있다.

\(S−>T\)는 생각해보면 절대 안된다. 그러면 각 상황에 대해 어떻게 판별할 건지 생각해보자.

\(S−>S\)의 경우에는 위의 선형 문제처럼 판별해줄 수 있다.

\(T−>T\)의 경우에는 사실 생각해보면 위의 선형 문제처럼 해도 상관없다는 것을 알 수 있다.

\(T−>S\)의 경우에는 살짝 특이한데 \(T−>S\) 가 되는 경우는 \(S\)가 \([T_s,\;N−1],\;[0,\;T_e]\)사이에 포함된다는 뜻으로, \(T\)선분을

\([T_s,\;N−1],\;[0\;,T_e]\)\(2\)개로 나누어서 선형문제처럼 판별해줄 수 있다.

각 상황별로 어떻게 처리할 지를 구상하였고, 이 상황을 \(T−>T\), \(T−>S\), \(S−>S\)순서로 처리해주면 된다.

2.소스 코드

#include <bits/stdc++.h>
#include <unordered_map>


using namespace std;


int n, m;
struct Line {
    int s, e, idx;
    bool rev;
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    cin >> n >> m;
    vector<Line> A, B;
    for (int i = 0; i < m; i++) {
        int s, e; cin >> s >> e;
        if (s <= e) A.push_back({ s, e, i });
        else B.push_back({s, e, i});
    }


    sort(B.begin(), B.end(), [](Line a, Line b) -> bool {
        if (a.s != b.s) return a.s < b.s;
        return a.e > b.e;
        });


    unordered_map<int, bool> vit;
    vector<Line> temp;
    int e = -1;
    for (Line& l : B) {
        if (vit[l.s]) continue;
        vit[l.s] = true;


        if (e == -1) {
            e = l.e;
            temp.push_back(l);
        }
        else {
            if (l.e > e) {
                temp.push_back(l);
                e = l.e;
            }
        }
    }


    vector<int> ans;
    for (Line& l : temp) {
        A.push_back({l.s, n-1, l.idx, true});
        A.push_back({0, l.e, l.idx, true});
        ans.push_back(l.idx);
    }


    sort(A.begin(), A.end(), [](Line a, Line b) -> bool {
        if (a.s != b.s) return a.s < b.s;
        if (a.e != b.e) return a.e > b.e;
        return a.rev > b.rev;
        });


    vit.clear(); e = -1;
    for (Line& l : A) {
        if (vit[l.s]) continue;
        vit[l.s] = true;


        if (e == -1) {
            e = l.e;
            ans.push_back(l.idx);
        }
        else {
            if (l.e > e) {
                ans.push_back(l.idx);
                e = l.e;
            }
        }
    }


    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());


    for (int w : ans) cout << w + 1 << " ";


    return 0;
}

3. 그리디 풀이

\(S\)노선은 그대로 두고, \(T\)노선을 적절한 방법으로 쪼갤 것인데, \(T\)노선을 \([T_s−N,\;T_e],\;[T_s,\;T_e+n]\)으로 쪼개고, 선형 문제처럼 처리하면 끝난다.

\([0,\;N−1]\)수직선을 \([−N+1,\;2N−1]\)수직선으로 확장하여 푼다는 것이다.

4. 소스 코드

#include <bits/stdc++.h>
#include <unordered_map>


using namespace std;


struct Line {
    int s, e, idx;
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    int n, m; cin >> n >> m;
    vector<Line> arr;
    for (int i = 0; i < m; i++) {
        int s, e; cin >> s >> e;
        if (s < e)
            arr.push_back({s, e, i});
        else {
            arr.push_back({ s-n, e, i });
            arr.push_back({ s, n + e, i });
        }
    }


    sort(arr.begin(), arr.end(), [](Line& a, Line& b) -> bool {
        if (a.s != b.s) return a.s < b.s;
        return a.e > b.e;
        });


    int e = -1;
    set<int> ans;
    for (Line& l : arr) {
        if (e == -1) {
            e = l.e;
            ans.insert(l.idx);
        }
        else if (e < l.e) {
            e = l.e;
            ans.insert(l.idx);
        }
    }
    for (int w : ans) cout << w + 1 << " ";


    return 0;
}