백준 19238 - 스타트 택시

문제링크

• 백준 19238

문제설명

• NxN 크기의 활동 영역과 M명의 승객의 위치와 각 승객의 목적지 좌표가 주어진다.
• 택시는 본인의 현재 위치에서 가장 가까운 승객을 찾아 이동하고, 해당 승객의 목적지까지 이동해야 연료를 충전할 수 있다.
• 즉, 소모되는 연료의 양은 택시->승객 + 승객->목적지 로 한 칸당 1의 연료가 필요하다.
• 승객을 목적지에 데려다주면 승객->목적지 로 이동하는 동안 사용한 연료의 2배만큼 충전한다.
• M명의 승객을 모두 데려다주었을 때 남은 연료의 양을 출력하라.
• M명의 승객을 모두 데려다줄 수 없을 때는 -1을 출력하라.

문제접근

• 승객들의 좌표와 각 승객의 목적지는 벡터 컨테이너로 관리한다. passengers[idx] 는 idx번 승객의 좌표, distInfo[idx] 는 idx번 승객의 목적지까지의 거리, arrived[idx] 는 idx번 승객을 태웠는지에 대한 유무를 나타낸다.
• BFS를 적용하여 택시와 가장 가까운 승객의 위치를 찾는다.
  • 택시는 벽(1)을 지나갈 수 없다.
  • 모든 좌표를 방문하며 승객을 만나면 가장 가까운 거리에 있는지 확인하고 태울 승객의 좌표를 갱신해야 한다.
  • 거리가 같은 경우 행 번호가 작은 승객을 먼저 태우고, 행 번호도 같다면 열 번호가 작은 승객을 먼저 태운다.
  • 이때, 택시의 위치와 승객의 위치가 같은 경우 도 고려해줘야 한다. 따라서 위 BFS를 적용하기 전에 택시 위치와 승객 위치를 먼저 비교한다. (놓쳤던 부분)
  • 택시가 승객에게 가지 못하는 경우가 있다. 이때는 방문할 좌표값이 갱신되지 않는다는 점을 이용하여 -1 을 출력하고 모든 로직을 종료한다.
• BFS를 적용하여 각 승객이 목적지까지 도달하는데 필요한 거리를 미리 계산한다.
  • 마찬가지로 벽(1)을 지나갈 수 없다. (놓쳤던 부분)
  • 목적지에 도달하면 목적지까지 이동한 거리를 return 하도록 하고, distInfo 벡터 컨테이너에 담아둔다.
  • 목적지까지 도달할 수 없다면 거리가 0으로 나타나게 되고, -1 을 출력하고 모든 로직을 종료한다. (놓쳤던 부분)
• 승객을 태우고 목적지까지 갔을 때 연료의 소모량을 계산한다.
  • 연료의 소모량은 택시->승객 + 승객->목적지 = minDist + distInfo[idx] 로 계산된다.
  • 남은 연료의 양이 0보다 작다면 -1 을 출력하고 모든 로직을 종료한다.
  • 남은 연료의 양이 0보다 크거나 같다면 distInfo[idx] x 2 만큼 남은 연료에서 연료를 충전한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, fuel;
int minX, minY, minDist;
int board[21][21] = { 0, }; // 길(0), 벽(1), 승객(2)
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int taxiX, taxiY;
vector<pair<int, int>> passengers;
vector<pair<int, int>> destinations;
int arrived[400] = { 0, };

// 현재 택시 위치에서 가장 가까운 승객을 찾는 완전탐색
void findNearPassenger() {
	minX = 100, minY = 100, minDist = 400;
	bool visited[21][21];
	int dist[21][21]; // 시작점에서 거리 정보
	memset(dist, 0, sizeof(dist));
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	q.push(make_pair(taxiX, taxiY));
	visited[taxiX][taxiY] = true;
	dist[taxiX][taxiY] = 0;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 1 || nextX > N || nextY < 1 || nextY > N) continue;
			if (board[nextX][nextY] == 1) continue;
			if (visited[nextX][nextY]) continue;
			visited[nextX][nextY] = true;
			q.push(make_pair(nextX, nextY));
			dist[nextX][nextY] = dist[cpos.first][cpos.second] + 1;
			if (board[nextX][nextY] == 2) { // 승객인 경우
				if (minDist > dist[nextX][nextY]) {
					minDist = dist[nextX][nextY];
					minX = nextX;
					minY = nextY;
				}
				else if (minDist == dist[nextX][nextY]) {
					if (minX > nextX) {
						minX = nextX;
						minY = nextY;
					}
					else if (minX == nextX) {
						if (minY > nextY) {
							minX = nextX;
							minY = nextY;
						}
					}
				}
			}
		}
	}
}

int getDistToDestination(int index) {
	bool visited[21][21];
	int dist[21][21];
	int x = passengers[index].first;
	int y = passengers[index].second;
	int destX = destinations[index].first;
	int destY = destinations[index].second;
	memset(dist, 0, sizeof(dist));
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 1 || nextX > N || nextY < 1 || nextY > N) continue;
			if (board[nextX][nextY] == 1) continue;
			if (visited[nextX][nextY]) continue;
			visited[nextX][nextY] = true;
			dist[nextX][nextY] = dist[cpos.first][cpos.second] + 1;
			q.push(make_pair(nextX, nextY));
			if (nextX == destX && nextY == destY) 
				return dist[destX][destY];
		}
	}
	return dist[destX][destY];
}

int getIndexPassenger() {
	for (int i = 0; i < M; i++) {
		if (arrived[i] == 1) continue;
		if (passengers[i].first == minX && passengers[i].second == minY) {
			return i;
		}
	}
	return -1;
}

void takeOffTaxi() {
	int cnt = 0;
	int idx = -1;
	// update distance info
	vector<int> distInfo;
	int val;
	for (int i = 0; i < M; i++) {
		val = getDistToDestination(i);
		distInfo.push_back(val);
	}

	while (true) {
		// printf("%d\n", fuel);
		if (cnt == M) break;
		if (board[taxiX][taxiY] == 2) {
			minX = taxiX;
			minY = taxiY;
			minDist = 0;
		}
		else 
			findNearPassenger(); // 가까운 승객 찾기

		if (minX == 100 && minY == 100) { // 접근이 불가능한 경우
			printf("-1\n"); 
			return;
		}

		idx = getIndexPassenger();
		arrived[idx] = 1;
		fuel -= minDist; // 택시 -> 승객
		fuel -= distInfo[idx]; // 승객 -> 목적지
		if (distInfo[idx] == 0) {
			printf("-1\n");
			return;
		}
		if (fuel < 0) {
			printf("-1\n");
			return;
		}
		fuel += (distInfo[idx] * 2);
		cnt++;
		taxiX = destinations[idx].first;
		taxiY = destinations[idx].second;
		board[minX][minY] = 0;
	}
	printf("%d\n", fuel);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &N, &M, &fuel);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			scanf("%d", &board[r][c]);
		}
	}
	scanf("%d %d", &taxiX, &taxiY);
	for (int i = 0; i < M; i++) {
		int x, y, fx, fy;
		scanf("%d %d %d %d", &x, &y, &fx, &fy);
		passengers.push_back(make_pair(x, y));
		destinations.push_back(make_pair(fx, fy));
		board[x][y] = 2;
	}
	takeOffTaxi();
	return 0;
}