스타트 택시 (feat. 백준, 19238번)

스타트 택시
https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/19238
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct Customer {
	int sx, sy, ex, ey;
};
int N, M, map[21][21], customer_map[21][21], dist[21][21], dx[4], dy[4], ans;
vector<Customer> customers;
pair<int, int> buf[21 * 21];
inline void my_merge_sort(register pair<int, int>* p, register int len) {
	if (len < 2)			return;
	register int i = 0, k = 0, mid = len / 2, j = mid;
	my_merge_sort(p, mid);
	my_merge_sort(p + mid, len - mid);
	while (i < mid && j < len) {
		if (p[i].first < p[j].first)
			buf[k++] = p[i++];
		else if ((p[i].first == p[j].first) && (p[i].second < p[j].second))
			buf[k++] = p[i++];
		else
			buf[k++] = p[j++];
	}
	while (i < mid)
		buf[k++] = p[i++];
	while (j < len)
		buf[k++] = p[j++];
	for (i = 0; i < len; ++i)
		p[i] = buf[i];
}
inline bool find_customer() {
	for (register int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			if (customer_map[ix][iy])		return true;
	return false;
}
inline void get_customer_destination(register int& sx, register int& sy, register int& ex, register int& ey) {
	for(register int i = 0; i < static_cast<int>(customers.size()); ++i)
		if (customers[i].sx == sx && customers[i].sy == sy) {
			ex = customers[i].ex, ey = customers[i].ey;
			return;
		}
}
inline bool goto_distance(register int& x, register int& y) {
	register int ex, ey, find_distance = static_cast<int>(1e9);
	for (register int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			dist[ix][iy] = -1;
	register queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	dist[x][y] = 0;
	get_customer_destination(x, y, ex, ey);							// 도착위치를 택시위치에 선반영
	if (x == ex && y == ey)											// 타자마자 내린 경우 (왜타냐...?)
		return true;
	while (!q.empty()) {
		register auto taxi_pos = q.front(); q.pop();
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = taxi_pos.first + dx[d], ny = taxi_pos.second + dy[d];
			if (1 <= nx && nx <= N && 1 <= ny && ny <= N && map[nx][ny] == 0 && dist[nx][ny] == -1) {
				dist[nx][ny] = dist[taxi_pos.first][taxi_pos.second] + 1;
				if (nx == ex && ny == ey) {
					if (find_distance > dist[nx][ny])
						find_distance = dist[nx][ny];
				}
				else
					if (find_distance == static_cast<int>(1e9) || find_distance == dist[nx][ny])
						q.push(make_pair(nx, ny));
			}
		}
	}
	ans -= find_distance;
	if (ans < 0) {												// 도착하는 곳에 도달하지 못하는 경우
		ans = -1;
		return false;
	}
	ans += find_distance << 1;
	x = ex, y = ey;
	return true;
}
inline bool find_customer(register int& x, register int& y) {
	if (!find_customer())			// 고객이 없으면 종료
		return false;
	register int find_distance = static_cast<int>(1e9);
	for (register int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			dist[ix][iy] = -1;
	register vector<pair<int, int>> candidates;
	register queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	dist[x][y] = 0;
	if (customer_map[x][y] == 1)									// 택시 위치에 손님이 있는 경우
	{
		customer_map[x][y] = 0;										// 고객 태웠으니 맵에서 삭제
		return goto_distance(x, y);
	}
	while (!q.empty()) {
		register auto taxi_pos = q.front(); q.pop();
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = taxi_pos.first + dx[d], ny = taxi_pos.second + dy[d];
			if (1 <= nx && nx <= N && 1 <= ny && ny <= N && map[nx][ny] == 0 && dist[nx][ny] == -1) {
				dist[nx][ny] = dist[taxi_pos.first][taxi_pos.second] + 1;
				if (customer_map[nx][ny]) {
					if (find_distance > dist[nx][ny])
						find_distance = dist[nx][ny], candidates.clear();
					if (find_distance == dist[nx][ny])
						candidates.push_back(make_pair(nx, ny));
				}
				else
					if (find_distance == static_cast<int>(1e9) || find_distance == dist[nx][ny])
						q.push(make_pair(nx, ny));
			}
		}
	}
	ans -= find_distance;
	if (ans <= 0 || candidates.empty()) {						// 가는데 연료가 바닥났거나 갈수있는곳에 손님이 없는 경우
		ans = -1;
		return false;
	}
	if (candidates.size() > 1)
		my_merge_sort(&candidates[0], candidates.size());
	x = candidates[0].first, y = candidates[0].second;			// 택시의 위치 반영
	customer_map[x][y] = 0;										// 고객 태웠으니 맵에서 삭제
	return goto_distance(x, y);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> M >> ans;
	for (register int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			cin >> map[ix][iy], customer_map[ix][iy] = 0;
	register int taxi_x, taxi_y;
	cin >> taxi_x >> taxi_y;
	register Customer customer;
	for (register int idx = 0; idx < M; ++idx)
		cin >> customer.sx >> customer.sy >> customer.ex >> customer.ey, customer_map[customer.sx][customer.sy] = 1, customers.push_back(customer);
	while (1)
		if (!find_customer(taxi_x, taxi_y))
			break;
	cout << ans << endl;
	return 0;
}
// *&)*@*

1. 택시가 출발하는 위치에 손님이 있을 수 있다는 것을 고려해야 합니다.
2. 택시가 도착하는 위치가 손님이 택시를 탔던 동일 자리일 수 있다는 것을 고려해야 합니다.
3. 택시가 손님을 못찾는 경우, -1을 리턴해야 합니다.
4. 택시가 도착점을 못찾는 경우, -1을 리턴해야 합니다.
5. 택시가 손님에게 가는 도중 (손님에게 도착한 것도 포함) 연료가 0이되면 종료되어야 합니다.
6. 택시가 도착점에게 가는 도중 (도착점에 도착했을때는 빼고) 연료가 0이되면 종료되어야 합니다.
7. 택시가 손님에게까지, 택시가 도착점까지 의 최단거리는 항상 업데이트 되어야 합니다.
8. 혹시 속도가 좀더 빨라질까하여 stl sort가 아닌 병합정렬을 만들어보았습니다. 백준서버상 차이는 없습니다.