[백준/BOJ] 백준 25243번 : 가희와 중부내륙선

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

25243번: 가희와 중부내륙선

 

우선순위 큐를 통해 시간의 흐름에 따라 열차를 배정하는 상황을 구현했다. 이때, 'used_time[u][v] = u ~ v 구간을 몇 시까지 사용하는지'를 이용해 특정 구간을 지금 배정하려는 열차에 배정할 수 있는지 판단하여 문제를 해결했다.

 

코드

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

int c, h;
vector<vector<int>> used_time(5, vector<int>(5, 0)); //[u][v] = u ~ v 구간을 몇시까지 사용하는지

//우선순위 (출발 시간순, 편성 번호 순)
priority_queue<tuple<int, int, int, int>> pq; //(-현재시간, -출발시간, -편성번호, 현재위치)

vector<pair<int, int>> result;

int CostTime(int here, int there) {
	if ((here == 0 && there == 1) || (here == 1 && there == 0)) {
		return 7;
	}

	else if ((here == 1 && there == 2) || (here == 2 && there == 1)) {
		return 7;
	}

	else if ((here == 2 && there == 3) || (here == 3 && there == 2)) {
		return 8;
	}

	return 10;
}

string MinToHour(int min_time) {

	int h = min_time / 60;
	int m = min_time % 60;

	if (h >= 24) {
		h -= 24;
	}

	string s_h;
	string s_m;

	//한자릿수일때
	if (h < 10) {
		s_h = "0" + to_string(h);
	}

	else {
		s_h = to_string(h);
	}

	//한자릿수일때
	if (m < 10) {
		s_m = "0" + to_string(m);
	}

	else {
		s_m = to_string(m);
	}

	return s_h + ":" + s_m;
}

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

	cin >> c >> h;

	for (int i = 0; i < c; i++) {
		int num;
		string start_time;
		cin >> num >> start_time;

		int i_start_time = (stoi(start_time.substr(0, 2)) * 60) + stoi(start_time.substr(3, 2));

		pq.push(make_tuple(-i_start_time, -i_start_time, -num, 0));
	}

	for (int i = 0; i < h; i++) {
		int num;
		string start_time;
		cin >> num >> start_time;

		int i_start_time = (stoi(start_time.substr(0, 2)) * 60) + stoi(start_time.substr(3, 2));

		pq.push(make_tuple(-i_start_time, -i_start_time, -num, 4));
	}

	while (!pq.empty()) {
		int here_time = -get<0>(pq.top());
		int start_time = -get<1>(pq.top());
		int here_num = -get<2>(pq.top());
		int here = get<3>(pq.top());
		pq.pop();

		if (here_num % 2 == 0) {//상행선 일때

			if (here == 0) { //도착 했을때
				result.push_back(make_pair(here_num, here_time));
				continue;
			}

			int there = here - 1;

			if (used_time[here][there] >= here_time) { //지금 해당 길을 이동할 수 없을때

				//1분 더 기다린다
				pq.push(make_tuple(-(here_time + 1), -start_time, -here_num, here));
			}

			else { //해당 길을 이동할 수 있을 때
				int cost = CostTime(here, there);

				used_time[here][there] = here_time + cost - 1; //해당 간선을 사용하는 시간
				used_time[there][here] = here_time + cost - 1;

				if (there != 0) { //최종 목적지가 아닐때, 1분 더 기다린다
					pq.push(make_tuple(-(here_time + cost + 1), -start_time, -here_num, there));
				}

				else {
					pq.push(make_tuple(-(here_time + cost), -start_time, -here_num, there));
				}
			}
		}

		else {//하행선일때

			if (here == 4) { //도착 했을때
				result.push_back(make_pair(here_num, here_time));
				continue;
			}

			int there = here + 1;

			if (used_time[here][there] >= here_time) { //지금 해당 길을 이동할 수 없을때

				//1분 더 기다린다
				pq.push(make_tuple(-(here_time + 1), -start_time, -here_num, here));
			}

			else { //해당 길을 이동할 수 있을 때
				int cost = CostTime(here, there);

				used_time[here][there] = here_time + cost - 1; //해당 간선을 사용하는 시간
				used_time[there][here] = here_time + cost - 1;

				if (there != 4) { //최종 목적지가 아닐때, 1분 더 기다린다
					pq.push(make_tuple(-(here_time + cost + 1), -start_time, -here_num, there));
				}

				else {
					pq.push(make_tuple(-(here_time + cost), -start_time, -here_num, there));
				}
			}
		}
	}

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

	for (int i = 0; i < result.size(); i++) {
		int here_time = result[i].second;
		cout << MinToHour(here_time) << "\n";
	}

	return 0;
}