[ boj : 22235 ] 가희와 수인 분당선 1

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

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

해설 : 하..........................................문제 똑바로 읽읍시다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

무려 하루 통채로 날려버렸네요 문제 똑바로 안읽어서 ㅠㅠㅠ

 

문제 자체가 까다로워 보이기도 하고, 되게 안읽혀서 뭐부터 어떻게 정리해야 될지 어떻게 시작해야 될지 너무 힘들었는데 결국 여기서 말려서 하루를 날렸습니다 ㅠㅠ

 

천천히 저랑 같이 조건들을 정리해 봐요 ㅠㅠㅠ(저같은 사람이 없었으면 하는 바람입니다)

 

1) 역들은 k210 부터 k272 까지 존재합니다.

 

2) 그러나 열차의 시작역하고 종착역은 정해져있습니다.(K210, K233, K246, K258, K272) 입니다. 

즉, 입력으로 주어지는 열차들의 정보는 전부 시작역과 종착역이 저 역들 중 하나입니다. 무조건!!!

 

3) 가희는 무조건 k225에서 출발해야합니다. 즉, 만약 열차들이 k255를 지나가지 않거나!! 또는 지나가지만 가희가 k225에 도착하는 시간보다 먼저 떠나버리면!!! 그 열차는 배제해 주면 됩니다.

 

4) 23:59:59 보다 더 넘게 인천역(k272)에 도착한다면 이건 도착하지 못한다고 판단하여 -1을 출력해줘야 합니다. 전 이것을 놓쳐서 하루를 날렸습니다....

 

5) HH:MM:SS 중 10보다 작으면 반드시 0을 앞에다가 붙여줘야 합니다.

 

6) 인천역에 도착할 수 없다면 -1을 출력해야합니다. 

 

전처리로 먼저 저장해줍시다. 무슨 말이냐면 [표1] 에 있는 역들을 제외한 역들은 2분씩 머무르고, 각 열차는 역에 도착하면 20초 후에 떠나가니

dp 배열을 선언하여서 각 역마다 얼만큼 있어야 떠나가는지를 미리 저장해주자라는 뜻입니다.

 

dp[i] = i 역에서 열차가 떠나가는 시간

 

그리고 이 dp 배열을 잘 이용해야되는데, 먼저 현재 도달한 역에 열차들이 지나가는지, 그리고 지나간다면 시간이 맞아 탑승할 수 있는지를 판단해주어야 합니다.

 

그림으로 보시죠.

만약 이해가 되시지 않으시다면 댓글로 남겨주세요.

 

결국은 이건 시작점이 k225이고 끝점이 k272 인 하나의 단방향 "그래프"로 나타낼 수 있습니다.

예제2 번을 모델링 하면

 

 

이렇게 표현이 가능하겠죠?

그렇다면 큐에 하나씩 넣어서 빼면서 k272에 도달한다면 답을 갱신해 주면 됩니다.

 

다만, 정말 주의해야 할 점은 "가희의 도착시점" 과 "열차가 떠나는 시점" 을 비교해 주어야 하는데 

현재 dp 배열에는 열차가 기다리는 시간 "20초"에 대한 정보를 넣어준 상태여서, "가희의 도착시점"을 구하려면 -20을 해주어서 비교해 주어야 합니다.

 

(혹시 틀린 내용이 있다면 댓글로 알려주시길 바라겠습니다,태클은 언제나 환영입니다.)

 

#include<bits/stdc++.h>

using namespace std;

struct info {
	int start, end, time;
};

const int inf = 0x3f3f3f3f;
int HH, MM, SS;
int arrive_time;
vector <info> v;
int dp[280], metro[280];
int visit[400];

int solve();
void init();
void input();

int main()
{
	input();
	init();
	int ret = solve();
	if (ret >= 86400) {
		cout << -1;
		return 0;
	}
	int div = 3600;
	string ans = "";
	for (int i = 0; i < 3; i++) {
		int t = ret / div;
		if (t < 10)
			ans += '0' + to_string(t);
		else
			ans += to_string(t);
		if (i != 2)ans += ":";
		ret %= div;
		div /= 60;
	}
	cout << ans;
	return 0;
}
int solve()
{
	int ans = inf;
	queue<info> q;
	for (int i = 0; i < v.size(); i++) {
		int start = v[i].start;
		int end = v[i].end;
		int s_time = v[i].time;

		//열차가 k225에서 떠나가는 시점, 도착한후 20초 후에 떠나감
		int leave_time = dp[225] - dp[start] + s_time;

		if ((start <= 225 && 225 < end) && arrive_time <= leave_time) {
			q.push({ start,end,dp[end] - dp[start] + s_time });
			visit[i] = 1;
		}
	}

	while (!q.empty())
	{
		info cur = q.front();
		q.pop();

		if (cur.end == 272) {
			ans = min(ans, cur.time - 20);
			continue;
		}
		for (int i = 0; i < v.size(); i++) {
			int start = v[i].start;
			int end = v[i].end;
			int s_time = v[i].time;

			if (visit[i])continue;

			int leave_time = dp[cur.end] - dp[start] + s_time;

			if ((start <= cur.end && cur.end < end) && cur.time - 20 <= leave_time) {
				q.push({ start, end,dp[end] - dp[start] + s_time });
				visit[i] = 1;
			}
		}
	}
	return ans;
}
void init()
{
	for (int i = 211; i <= 272; i++)
		metro[i] = 2;
	metro[211] = 3; metro[221] = 4; metro[222] = 4; metro[223] = 3; metro[226] = 3; metro[239] = 3; metro[246] = 4; metro[248] = 5; metro[250] = 4; metro[251] = 3; metro[257] = 3; metro[267] = 3;

	for (int i = 211; i <= 272; i++)
		dp[i] = dp[i - 1] + (metro[i] * 60 + 20);
}
void input()
{
	char x[5], y[5], z[6], moran[30];
	int n;
	cin >> moran >> n;
	HH = atoi(moran), MM = atoi(moran + 3), SS = atoi(moran + 6);
	arrive_time = HH * 3600 + MM * 60 + SS;

	for (int i = 0; i < n; i++) {
		cin >> x >> y >> z;
		int ix = atoi(x + 1);
		int iy = atoi(y + 1);
		int hh = atoi(z), mm = atoi(z + 3);
		int time = (hh * 3600) + (mm * 60) + 0;
		v.push_back({ ix,iy,time });
	}
}