[BOJ] 백준 10165. 버스 노선 (Platinum V)

KOI 2014 초등부, 중등부, 고등부 모든 부문에 출제된 문제이다.

초등부 입장에선 꽤나 어려웠을 것 같은 문제.

https://www.acmicpc.net/problem/10165

10165번: 버스 노선

---

의식의 흐름 및 해설

시계, 반시계의 표현으로 헷갈리게 표현했지만, 결국은

a->b의 방향으로, a>b일 경우 a->(b+N)의 방향으로 간다는 점만 생각하면 된다.

 

우리를 자주 괴롭히는 원형(circular) 문제이다.

원형으로 문제가 나올 경우, 직선에 비해 난이도가 최소 1.5배는 뛰는 것 같다.

원형 문제는 대체로 직선으로 풀어서 생각하되, 시작점이 끝점이 될 수 있다는 반복되는 부분 때문에 둘레를 펼친 직선을 두 개 연속으로 놓아 생각해야 한다.

이 문제 역시, 원을 펼쳐서 직선으로 생각하되, 시작점이 끝점이 될 수 있기 때문에 직선을 두 개 연속하게 이어서 놓도록 하자.

 

이 문제의 예제를 보면서 설명하도록 하겠다.

10
5
0 4
2 6
5 0
7 9
9 4

a>b인 경우에서 b=b+N으로 변환하여 쓰면 아래와 같다.

10
5
0 4
2 6
5 10
7 9
9 14

위에서 말한 것과 같이 두 직선을 이어 연속하게 놓는다면,

0~4, 2~6, 5~10, 7~9는 10~14, 12~16, 15~20, 17~19 또한 생길 것이다.

 

이 경우를 고려하는 이유는 0~4는 9~14에 완전히 포함돼야 하는데, 0~4만 고려한다면 9~14와 같이 반시계 방향으로 연장되는 노선에 포함되는 경우를 고려하지 못하기 때문에 10~14와 같이 a+N ~ b+N 노선을 만들어줘야 한다.

 

5~0 (5~10, 15~20)은 생기지 않아도 상관 없다. 그 이유는 우리가 10~14, 12~16과 같이 a+N ~ b+N을 만드는 이유가 반시계 방향으로 연장되는 노선에 포함되는 노선이 있을까봐 만드는 것인데, 

반시계 방향으로 연장되는 노선에 20이 있다면 그 노선의 길이는 한바퀴 이상이기 때문에 불가능하다. 따라서 반시계 방향 노선 (5~0 또는 5~10)에는 +N을 한 노선을 만들 필요가 없다.

 

그 이후 풀이는 평범한 스위핑과 일치한다.

다만, 주의할 점은 스위핑을 하게 위해 sort를 할 때, 시작점이 같을 경우, 끝점은 오름차순으로 정렬해야 한다.

 

두 노선 0 5, 0 3 이 있다고 가정하자. 

0 3, 0 5 순으로 정렬된다면, 0 5 차례로 넘어갈 때, 0 3 은 이미 탐색이 완료됐으므로, 0 5 안에 포함되는 것을 체크하지 못하고 넘어갈 것이기 때문이다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef pair<int, int> pi;
const int MAX = 500011;
int N, M;
vector<pair<pi, int>> v;
bool visit[MAX];
bool cmp(pair<pi, int> p1, pair<pi, int> p2) {
	if (p1.first.first == p2.first.first)
		return p1.first.second > p2.first.second;
	return p1.first.first < p2.first.first;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		if (a < b) {
			v.push_back({ {a,b}, i });
			v.push_back({{ a + N, b + N }, i});
		}
		else
			v.push_back({ { a, b + N }, i });
	}
	sort(all(v), cmp);
	int s = 0, e = 0, left = 0, right = 0;
	for (int i = 0; i < v.size(); i++) {
		s = v[i].first.first;
		e = v[i].first.second;
		int idx = v[i].second;
		if (visit[idx])
			continue;
		if (left <= s && e <= right) {
			visit[idx] = true;
			continue;
		}
		left = s;
		right = e;
	}
	for (int i = 0; i < M; i++) {
		if (!visit[i])
			cout << i + 1 << " ";
	}
}

---

난이도 기여 창에 가고 나서 놀랐던 점이 두 가지가 있다.

하나는 이 문제의 알고리즘 분류가 '그리디' 뿐이었다는 점,

다른 하나는 이 문제의 난이도 투표 기여에 Platinum IV ~ Platinum V가 압도적으로 많았다는 점.

 

나는 이 문제의 알고리즘 분류가 그리디보다는 스위핑에 가깝다고 생각하며,

적정 티어는 Gold I ~ Gold II 정도라 본다.

 

다만, 원형일 때의 적절한 아이디어를 처리하는 데에 익숙하지 않다면 체감난이도가 올라갈 것이기 때문에 Platinum 난이도로 투표된 것도 충분히 이해된다.

 

역시 ps(코딩테스트)는 많이 풀어보고 충분히 수련하면서 실력을 늘려야 하는 듯.