[백준/BOJ] 백준 22235번 : 가희와 수인 분당선 1

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

22235번: 가희와 수인 분당선 1

각 역에서 기차가 떠나는 시간의 경우들을 저장해 놓고, 225역에서 출발 시간에 출발하여 272역에 도착할 때까지 탈 수 있는 가장 빠른 기차들을 타는 경우를 고려하여 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <set>
using namespace std;

string begin_time;
int n;
set<int> leave_sec[300]; //각 역에서 언제 떠나는지 저장
set<int>::iterator it;
vector<int> moving(300, 120);

//해당 역에서 다음역으로 이동하는데 걸리는 시간을 저장한다
void MakeMoving()
{
	moving[210] = 3 * 60;
	moving[220] = 4 * 60;
	moving[221] = 4 * 60;
	moving[222] = 3 * 60;
	moving[225] = 3 * 60;
	moving[238] = 3 * 60;
	moving[245] = 4 * 60;
	moving[247] = 5 * 60;
	moving[249] = 4 * 60;
	moving[250] = 3 * 60;
	moving[256] = 3 * 60;
	moving[266] = 3 * 60;
}

int TimeSec(string input)
{
	stringstream ss(input);
	string temp;
	vector<string> check;

	while (getline(ss, temp, ':'))
	{
		check.push_back(temp);
	}

	int ret = 0;

	ret += (stoi(check[0]) * 3600);
	ret += (stoi(check[1]) * 60);

	return ret;
}

string SecTime(int input)
{
	string HH;
	string mm;
	string ss;

	ss = to_string(input % 60);
	input /= 60;
	mm = to_string(input % 60);
	input /= 60;
	HH = to_string(input);

	if (HH.size() == 1)
		HH = '0' + HH;
	if (mm.size() == 1)
		mm = '0' + mm;
	if (ss.size() == 1)
		ss = '0' + ss;

	return HH + ':' + mm + ':' + ss;
}

void Visite(string start_point, string end_point, string start_time)
{
	string start_number_s = start_point.substr(1, 3);
	string end_number_s = end_point.substr(1, 3);

	int start_number = stoi(start_number_s);
	int end_number = stoi(end_number_s);
	int here_sec = TimeSec(start_time);

	leave_sec[start_number].insert(here_sec);
	for (int i = start_number; i < end_number; i++)
	{
		int left = i;
		int right = i + 1;
		int moving_sec = moving[left];

		//right에 here_time + moving_time 에 도착해서, 20초 후에 떠남
		leave_sec[right].insert(here_sec + moving_sec + 20);

		//현재 시간은 움직이는 시간, 20초 머무는 시간이 추가 되었다
		here_sec += (moving_sec + 20);
	}
}

int Solve(int here_point, int here_sec)
{
	//목적지에 도착 했을때
	if (here_point == 272)
		return here_sec;

	//현재시간이 here_sec라면
	//here_sec이후에 떠나는것중 가장 빠른거를 타야한다

	//here_point에서 떠나는 열차가 없을때
	if (leave_sec[here_point].size() == 0)
		return -1;

	//here_sec보다 큰것중 가장 작은거를 구한다
	it = leave_sec[here_point].upper_bound(here_sec);

	//탈 수 있는 열차가 없을때
	if (it == leave_sec[here_point].end())
		return -1;

	return Solve(here_point + 1, *it + moving[here_point]);
}

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

	MakeMoving();

	cin >> begin_time;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string start_point;
		string end_point;
		string start_time;

		cin >> start_point >> end_point >> start_time;
		Visite(start_point, end_point, start_time);
	}

	int begin_sec = TimeSec(begin_time);

	int result = Solve(225, begin_sec);;

	if (result == -1 || result > (23 * 3600) + (59 * 60) + (59))
		cout << -1;
	else
		cout << SecTime(result);

	return 0;
}