[C++] 백준 19238번 스타트 택시

19238번: 스타트 택시

삼성 SW 역량 테스트 기출 문제 수록 문제.

구현 + 시뮬레이션 + 그래프 탐색 알고리즘으로 풀 수 있다.

 

문제 해석

택시의 조건은 다음과 같다.

• 목적지에 도착 시, 연료가 충전된다.
• 연료가 바닥날 경우 업무가 끝난다.
• 택시는 빈 칸의 상, 하, 좌, 우로 이동하며 특정 위치에 최단 경로로만 이동한다.
• 연료는 이동 한 칸마다 1이 소모된다.

다른 조건들은 다음과 같다.

• M명의 승객을 태우는 것을 목표로 한다.
• 활동 영역은 N x N이며, 각각의 칸은 비어있거나 벽이 된다.
• M명의 승객은 빈 칸 중 하나에 있으며 다른 칸들 중 하나로 이동한다.
  이 때, 여러 승객이 동승하지는 않는다.
• 승객 선택은 최단 거리, 행 번호 작은 승객, 열 번호 작은 승객
  순서대로 선택한다.
• 손님을 태우고 목적지까지 이동한 거리가 r일 때,
  목적지에 도달할 시, 2 x r만큼 연료가 충전된다.

 

또한, 이동 중 연료가 바닥날 경우 이동에 실패한 것으로 간주하며, 업무가 종료된다.

 

문제 접근

첫 번째 접근

• 우선 순위 큐에 손님 구조체를 넣어서 현재 택시와의 거리, 손님의 r, 손님의 c를 통해 정렬한다.

구조체를 통해 손님과 택시의 정보를 저장했다.

하지만 우선 순위 큐에서는 이미 정렬이 된 상태로 저장돼서, 택시가 이동했을 때를 고려할 수 없었다.

따라서 해당 방식으로는 풀 수 없었다.

 

두 번째 접근

• 정렬 메서드를 만들어서 i번 째 손님을 태울 때마다 정렬한다.

방식이 비슷하게 맞았지만, 나 같은 경우 손님과 택시의 거리를 |r1 - r2| + |c1 - c2|로 구했어서 틀렸었다.

왜냐하면 벽이 있을 수 있기 때문이다. 그래서 bfs를 통해 거리를 구해야 하는데,

그래프 탐색의 경우 최대 20 * 20인 400만큼 탐색할 수 있다.

또한 손님 벡터를 정렬 하는 데에는 매 번 그래프 탐색이 필요하므로

400(전체 손님) * 400(손님 비교1) * 400(손님 비교2) = 64,000,000번의 연산이 필요하다.

매 번 정렬을 하게될 경우, 400(손님 수) * 64,000,000 이므로 시간 초과가 발생한다.

 

세 번째 접근

• 선택 정렬과 비슷한 개념으로 정렬 후 구하는 방식.

매 번 index에 맞는 손님을 목적지에 태웠다는 가정 하에 다음 index에 해당하는 손님들을 찾는 방식.

첫 번째 index에 맞는 손님을 저장하고,

두 번째 index에 맞는 손님을 저장하고, ...

총 정렬하는 데에 필요한 연산 수는 64,000,000번의 연산이 필요하다.

 

하지만 더 나아가서 현재 index에 맞는 손님을 찾았다면 바로 택시를 이동시켜도 된다.

 

코드 본문

/*
* 백준 19238번 스타트 택시
* https://www.acmicpc.net/problem/19238
* - 구현 / 시뮬레이션 / 그래프 탐색 : BFS
*/
#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

struct Customer {
	int startR, startC;
	int destR, destC;
};

struct Taxi {
	int curR, curC;
	int curFuel;
};

Taxi taxi = { 0, 0, 0 };

vector<Customer> customerVec;
int widthHeight, customerCnt;
int map[21][21];
bool cantGo;

pair<int, int> directions[4] = {
	{1, 0},
	{-1, 0},
	{0, 1},
	{0, -1}
};


int getDistanceToDestination(int destR, int destC) {
	bool visit[21][21];

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			visit[i][j] = false;
		}
	}

	visit[taxi.curR][taxi.curC] = true;
	queue<pair<pair<int, int>, int>> q;
	q.push({ {taxi.curR, taxi.curC}, 0 });

	while (!q.empty()) {
		int curR = q.front().first.first;
		int curC = q.front().first.second;
		int curDist = q.front().second;
		q.pop();

		if (curR == destR && curC == destC) {
			return curDist;
		}

		for (pair<int, int> direction : directions) {
			int nxtR = curR + direction.first;
			int nxtC = curC + direction.second;
			int nxtDist = curDist + 1;

			if (nxtR < 1 || nxtR > widthHeight || nxtC < 1 || nxtC > widthHeight
				|| visit[nxtR][nxtC] || map[nxtR][nxtC] == 1) continue;

			visit[nxtR][nxtC] = true;

			q.push({ {nxtR, nxtC}, nxtDist });
		}
	}

	return -1;
}
void go() {
	for (int i = 0; i < customerCnt; i++) {
		Customer selectCustomer = customerVec[i];

		for (int j = i + 1; j < customerCnt; j++) {
			Customer checkCustomer = customerVec[j];
			int c1DistanceFromTaxi = getDistanceToDestination(selectCustomer.startR, selectCustomer.startC);
			int c2DistanceFromTaxi = getDistanceToDestination(checkCustomer.startR, checkCustomer.startC);

			if (c1DistanceFromTaxi == -1) {
				customerVec[i] = checkCustomer;
				customerVec[j] = selectCustomer;
				selectCustomer = checkCustomer;
			}
			else if (c1DistanceFromTaxi != -1 && c1DistanceFromTaxi > c2DistanceFromTaxi) {
				customerVec[i] = checkCustomer;
				customerVec[j] = selectCustomer;
				selectCustomer = checkCustomer;
			}
			else if (c1DistanceFromTaxi == c2DistanceFromTaxi) {
				if (selectCustomer.startR > checkCustomer.startR) {
					customerVec[i] = checkCustomer;
					customerVec[j] = selectCustomer;
					selectCustomer = checkCustomer;
				}
				else if (selectCustomer.startR == checkCustomer.startR) {
					if (selectCustomer.startC > checkCustomer.startC) {
						customerVec[i] = checkCustomer;
						customerVec[j] = selectCustomer;
						selectCustomer = checkCustomer;
					}
				}
			}
		}

		int needFuelToCustomer = getDistanceToDestination(selectCustomer.startR, selectCustomer.startC);

		//cout << "needCustomer : " << customer.startR << " , " << customer.startC << "\n";

		if (taxi.curFuel < needFuelToCustomer || needFuelToCustomer == -1) {
			cantGo = true;
			return;
		}

		taxi.curFuel -= needFuelToCustomer;
		taxi.curR = selectCustomer.startR;
		taxi.curC = selectCustomer.startC;

		int needFuelToDestination = getDistanceToDestination(selectCustomer.destR, selectCustomer.destC);

		if (taxi.curFuel < needFuelToDestination || needFuelToDestination == -1) {
			cantGo = true;
			return;
		}

		taxi.curFuel -= needFuelToDestination;
		taxi.curR = selectCustomer.destR;
		taxi.curC = selectCustomer.destC;

		taxi.curFuel += (2 * needFuelToDestination);

		taxi.curR = selectCustomer.destR;
		taxi.curC = selectCustomer.destC;
	}
}

int main() {
	cin >> widthHeight >> customerCnt >> taxi.curFuel;

	for (int r = 1; r <= widthHeight; r++) {
		for (int c = 1; c <= widthHeight; c++) {
			cin >> map[r][c];
		}
	}

	cin >> taxi.curR >> taxi.curC;

	for (int i = 1; i <= customerCnt; i++) {
		Customer customer = { 0, 0, 0, 0 };
		cin >> customer.startR >> customer.startC >> customer.destR >> customer.destC;

		customerVec.push_back(customer);
	}

	go();

	if (cantGo) {
		cout << -1;
	}
	else {
		cout << taxi.curFuel;
	}

	return 0;
}