[백준/BOJ] 백준 10165번 : 버스 노선

www.acmicpc.net/problem/10165

10165번: 버스 노선

시작점이 더 작은 숫자인 버스는 bus1에 저장하고, 시작점이 더 큰 숫자인 버스는 bus2에 저장하였다. 그리고 bus1, bus2를 시작점이 작은 게 앞에 오고, 시작점이 같다면 도착점이 큰 게 앞에 오도록 정렬을 했다. 주의해야 될 점은 bus2는 도착지점에 n을 더한 것을 만든 뒤 그것을 앞에서 말한 형식에 맞춰 정렬했다. 그리고, bus1에 의해 사라지는 bus1을 제외한 maked_bus1, bus2에 의해 사라지는 bus2를 제외한 maked_bus2를 구한다. 그리고 bus1의 버스로는 bus2의 버스를 지울수 없지만 bus2의 버스로는 bus1의 버스를 지울 수 있다는 것을 이용해 bus2에 의해 지워지는 bus1을 제외한 bus1을 저장한 maked_maked_bus1를 구해서 문제를 해결했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
#include <map>
using namespace std;

int n, m;
vector<pair<int, int>> bus1; //시작점이 작은 숫자인 버스
vector<pair<int, int>> bus2; //시작점이 큰 숫자인 버스
vector<pair<int, int>>::iterator it;
map<pair<int, int>, int> bus_number;
vector<int> result;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	//시작 점이 작은게 앞에 오도록
	if (a.first < b.first)
		return true;

	//시작점이 같다면 도착점이 큰게 앞에 오도록
	else if (a.first == b.first)
	{
		if (a.second > b.second)
			return true;
	}

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	cin >> m;

	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;

		if (a < b)
			bus1.push_back(make_pair(a, b));
		else
			bus2.push_back(make_pair(a, b));

		bus_number.insert(make_pair(make_pair(a, b), i));
	}

	sort(bus1.begin(), bus1.end(), cmp);

	vector<pair<int, int>> maked_bus1; //bus1에 의해 사라지는 버스를 제외한 bus1
	int before_bus1_max_dist = -1; //이전 bus1중 가장 큰 목적지

	for (int i = 0; i < bus1.size(); i++)
	{
		if (before_bus1_max_dist >= bus1[i].second) //bus1[i]는 지워진다
			continue;
		else
		{
			maked_bus1.push_back(bus1[i]);
			before_bus1_max_dist = bus1[i].second;
		}
	}

	vector<pair<int, int>> new_bus2; //도착지점에 n을 더한것을 만든다 (도착지점을 더 크게 만들기 위해)
	for (int i = 0; i < bus2.size(); i++)
	{
		new_bus2.push_back(make_pair(bus2[i].first, bus2[i].second + n));
	}

	sort(new_bus2.begin(), new_bus2.end(), cmp);

	vector<pair<int, int>> maked_bus2; //bus2에 의해 사라지는 버스를 제외한 bus2
	int before_new_bus2_max_dist = -1; //이전 new_bus2중 가장 큰 목적지
	
	for (int i = 0; i < new_bus2.size(); i++)
	{
		if (before_new_bus2_max_dist >= new_bus2[i].second) //new_bus2[i]는 지워진다
			continue;
		else
		{
			maked_bus2.push_back(make_pair(new_bus2[i].first, new_bus2[i].second - n));
			before_new_bus2_max_dist = new_bus2[i].second;
		}
	}

	//bus1의 버스로는 bus2의 버스를 지울수 없지만 bus2의 버스로는 bus1의 버스를 지울 수 있다
	int bus2_min_start = 987654321; //bus2의 가장 작은 시작점을 저장
	int bus2_max_dist = -1; //bus2의 가장 큰 도착점을 저장
	for (int i = 0; i < maked_bus2.size(); i++)
	{
		bus2_min_start = min(bus2_min_start, maked_bus2[i].first);
		bus2_max_dist = max(bus2_max_dist, maked_bus2[i].second);
	}

	vector<pair<int, int>> maked_maked_bus1; //bus2에 의해 지워지는 bus1을 제외한 bus1

	if (maked_bus2.size() != 0)
	{
		for (int i = 0; i < maked_bus1.size(); i++)
		{
			//bus1의 도착점이 bus2에서 가장 큰 도착점 보다 작을때 (bus2의 시작점은 모두 0 왼쪽에 있으므로)
			if (bus2_max_dist >= maked_bus1[i].second)
				continue;

			//bus1의 시작점이 bus2에서 가장 작은 시작점 보다 클때 (bus2의 도착점은 모두 0 또는 0 오른쪽에 있으므로)
			else if (bus2_min_start <= maked_bus1[i].first)
				continue;

			else
				maked_maked_bus1.push_back(maked_bus1[i]);
		}
	}


	for (int i = 0; i < maked_maked_bus1.size(); i++)
	{
		int this_bus_number = bus_number[maked_maked_bus1[i]];
		result.push_back(this_bus_number);
	}

	for (int i = 0; i < maked_bus2.size(); i++)
	{
		int this_bus_number = bus_number[maked_bus2[i]];
		result.push_back(this_bus_number);
	}


	sort(result.begin(), result.end());

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";


	return 0;
}