[BOJ] 19238 스타트 택시 (C/C++)

19238번: 스타트 택시

---

오랜만이라 반가운 BFS 문제였다. 문제는 복잡하거나 구현할 것이 많다거나 하지는 않았다. 택시가 동시에 여러 명을 태우고 다녔으면 그건 좀 골치 아팠을 것 같다. 하지만 이 문제는 택시에 한 번에 한 명밖에 태울 수 없기 때문에 그리디하게 풀면 되는 문제였다.

 

택시의 운행 알고리즘은 엄청 심플하다.

1	현재 택시 위치에서 가장 가까운 승객을 찾는다.
2	그 승객을 태우고 도착점까지 최단 거리로 운행한다.

이 과정에서 연료가 다 떨어지면 택시는 더 이상 운행할 수 없다. 1번과 2번에서 최단 거리를 찾기 위해서 BFS를 사용했다. 

 

처음에는 입력을 받을 때 각 승객마다 필요한 운행 거리를 미리 구해놨었다. 만약 승객이 택시를 여러번 탄다면 의미 있는 행동이었겠지만 이 문제에서는 승객이 택시를 한 번만 타고 제외되므로 오히려 lazy하게 거리를 구하는 것이 오버헤드를 줄일 수 있는 방법이었다. 

 

또한, 이 문제에서 이동할 수 없는 벽이 1로 주어진다. 나 같은 경우엔 좌표 상의 0보다 큰 숫자를 해당 좌표에 있는 승객의 번호로 사용했기 때문에 벽을 1이 아니라 -1로 사용했다. 

 

운행을 완료하기 위해서는 승객을 태우러 가는 동안의 연료와 승객을 태우고 도착점까지 가는 동안의 연료가 필요하다. 만약 현재 연료가 그보다 부족하다면 flag를 set하고 -1을 출력했다. 

 

문제에 예시로 주어진 입력 중에 마지막은 아예 지도가 반으로 갈라진 상태이다. 따라서 이동할 수 없음을 나타내는 무한한 값이 필요해서 해당 값을 987654321으로 사용했다.

 

그리고 이 문제에서는 최단 거리가 같은 승객끼리의 우선 순위가 정해져있다. 처음엔 따로 처리를 해주지 않고도 처음에 찾은 승객을 무조건 탑승시킬 수 있도록 할 수 있을 것 같았다. 그런데 잘 되지 않아서 따로 우선 순위를 처리하고 정답을 받았다. 이후에 다른 분들의 코드를 살펴봤을 때에는 딱히 뾰족한 수가 없어보였다.

 

	#include <iostream>
	#include <queue>
	#include <cstring>
	using namespace std;
	#define MAX_N 21
	#define MAX_M MAX_N * MAX_N
	#define INF 987654321
	typedef struct _PERSON {
	int sx, sy, dx, dy;
	} person_t;
	typedef struct _POINT {
	int x, y, d;
	} point_t;
	const int next_x[] = { -1, 0, 0, 1 };
	const int next_y[] = { 0, -1, 1, 0 };
	int N, M, fuel, car_x, car_y;
	int map[MAX_N][MAX_N];
	person_t person[MAX_M];
	int getDistance(int sx, int sy, int dx, int dy) {
	queue<point_t> q;
	bool visit[MAX_N][MAX_N];
	memset(visit, false, sizeof(visit));
	q.push({ sx, sy, 0});
	visit[sx][sy] = true;
	while (!q.empty()) {
	int cur_x = q.front().x;
	int cur_y = q.front().y;
	int cur_dist = q.front().d;
	q.pop();
	if (cur_x == dx && cur_y == dy)
	return cur_dist;
	for (int dir = 0; dir < 4; dir++) {
	int nx = cur_x + next_x[dir];
	int ny = cur_y + next_y[dir];
	// 유효한 좌표인지 검사
	if (0 < nx && nx <= N && 0 < ny && ny <= N) {
	// 벽이거나 이미 방문했다면 방문하지 않음
	if (map[nx][ny] == -1 || visit[nx][ny]) continue;
	q.push({ nx, ny, cur_dist + 1 });
	visit[nx][ny] = true;
	}
	}
	}
	return INF;
	}
	int getNearestPassenger(int sx, int sy, int *dist) {
	queue<point_t> q;
	bool visit[MAX_N][MAX_N];
	int p_num = -1;
	int min_dist = INF;
	memset(visit, false, sizeof(visit));
	q.push({ sx, sy, 0 });
	visit[sx][sy] = true;
	while (!q.empty()) {
	int cur_x = q.front().x;
	int cur_y = q.front().y;
	int cur_dist = q.front().d;
	q.pop();
	// 아직 택시를 탑승하지 않은 승객이 있는 좌표
	if (map[cur_x][cur_y] > 0) {
	if (min_dist > cur_dist) {
	p_num = map[cur_x][cur_y];
	min_dist = cur_dist;
	}
	else if (min_dist == cur_dist) {
	int min_x = person[p_num].sx;
	int min_y = person[p_num].sy;
	// 행이 작은 승객부터
	if (min_x > cur_x) {
	p_num = map[cur_x][cur_y];
	}
	// 행도 같다면 열이 작은 승객부터
	else if (min_x == cur_x && min_y > cur_y) {
	p_num = map[cur_x][cur_y];
	}
	}
	}
	for (int dir = 0; dir < 4; dir++) {
	int nx = cur_x + next_x[dir];
	int ny = cur_y + next_y[dir];
	// 유효한 좌표인지 검사
	if (0 < nx && nx <= N && 0 < ny && ny <= N) {
	// 벽이거나 이미 방문했다면 방문하지 않음
	if (map[nx][ny] == -1 || visit[nx][ny]) continue;
	q.push({ nx, ny, cur_dist + 1 });
	visit[nx][ny] = true;
	}
	}
	}
	*dist = min_dist;
	return p_num;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> fuel;
	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
	cin >> map[i][j];
	if (map[i][j] == 1) map[i][j] = -1;
	}
	cin >> car_x >> car_y;
	int sx, sy, dx, dy;
	for (int i = 1; i <= M; i++) {
	cin >> sx >> sy >> dx >> dy;
	map[sx][sy] = i;
	person[i] = { sx, sy, dx, dy};
	}
	bool flag = true;
	for(int i = 1; i <= M; i++) {
	int c2s_dist, s2e_dist;
	int p_num = getNearestPassenger(car_x, car_y, &c2s_dist);
	// 태울 수 있는 승객이 없는 경우
	if (p_num == -1) {
	flag = false;
	break;
	}
	sx = person[p_num].sx; sy = person[p_num].sy;
	dx = person[p_num].dx; dy = person[p_num].dy;
	// 승객의 시작점과 도착점 사이의 거리
	s2e_dist = getDistance(sx, sy, dx, dy);
	fuel = fuel - c2s_dist - s2e_dist;
	// 택시 운행에 필요한 연료가 부족한 경우
	if (fuel < 0) {
	flag = false;
	break;
	}
	// 승객의 도착점으로 택시의 좌표 변경
	car_x = person[p_num].dx; car_y = person[p_num].dy;
	// 지도에서 승객 삭제
	map[person[p_num].sx][person[p_num].sy] = 0;
	// 연료 충전
	fuel = fuel + s2e_dist * 2;
	}
	if (!flag)
	fuel = -1;
	cout << fuel << "\n";
	return 0;
	}

view raw 19238.cpp hosted with ❤ by GitHub

 

 

후기)

오랜만에 좌표 상에서 최단 거리 문제를 풀라고하니까 바로 BFS가 떠오르지 않았다. 처음엔 DFS로 시도하다가 갑자기 생각나서 방법을 바꿨다... 그나마 다행인 점은 구현하는 데 있어서 실수를 하지는 않았다.