백준 19238번 스타트 택시

sol : 115' 12''

• 수행 시간 : 4ms
• 메모리 : 2028KB

Learnings

• 내 맘대로 판단하지 말자.
• BFS는 최단거리만 보장해줄 뿐, 실제로는 부모 q에 의존하여 자식 q가 방향 우선순위를 지키지 못하는 경우가 존재한다.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <tuple>
#include <climits>

using namespace std;

#define MAX_N 21
#define EMPTY 0
#define WALL 1
#define NOT_VISITED -1

int n, m;
// 상, 좌, 하, 우
const int ds[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
int grid[MAX_N][MAX_N];
int startGrid[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
int curPId;
int remainedPassengerNum;

struct Taxi {
	int r;
	int c;
	long long remainedGas;

	Taxi() {}
};

struct Passenger {
	int di;
	int dj;

	Passenger() {}
	Passenger(int _di, int _dj) :
		di(_di), dj(_dj) {
	}
};

Taxi taxi;
vector<Passenger> destIndices;

void InitDist() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j] = NOT_VISITED;
		}
	}
}

void Init() {
	int gas;
	cin >> n >> m >> gas;
	taxi.remainedGas = gas;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}

	cin >> taxi.r >> taxi.c;

	destIndices.resize(m + 1);
	for (int i = 1; i <= m; i++) {
		int si, sj, di, dj;
		cin >> si >> sj >> di >> dj;
		startGrid[si][sj] = i;
		destIndices[i] = Passenger(di, dj);
	}

	remainedPassengerNum = m;
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

bool FindClosest() {
	InitDist();
	int ci = taxi.r, cj = taxi.c;
	curPId = -1;

	queue<pair<int, int>> q;
	q.push({ ci, cj });
	dist[ci][cj] = 0;
	tuple<int, int, int> target = { INT_MAX, INT_MAX, INT_MAX };

	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		if (startGrid[ci][cj] > 0) {
			tuple<int, int, int> curP = { dist[ci][cj], ci, cj };
			if (curP < target) {
				target = curP;
				curPId = startGrid[ci][cj];
			}
		}

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (!InGrid(ni, nj)) continue;
			if (grid[ni][nj] == WALL) continue;
			if (dist[ni][nj] != NOT_VISITED) continue;
			if (dist[ci][cj] + 1 > taxi.remainedGas) continue;

			dist[ni][nj] = dist[ci][cj] + 1;
			q.push({ ni, nj });
		}
	}

	if (curPId == -1) return false;
	else {
		int curD, curi, curj;
		tie(curD, curi, curj) = target;

		taxi.remainedGas -= curD;
		startGrid[curi][curj] = 0;
		taxi.r = curi, taxi.c = curj;
	}
	return true;
}

bool Transport() {
	int ci = taxi.r, cj = taxi.c;
	InitDist();
	queue<pair<int, int>> q;

	q.push({ ci, cj });
	dist[ci][cj] = 0;

	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		if (ci == destIndices[curPId].di && cj == destIndices[curPId].dj) {
			taxi.remainedGas += dist[ci][cj];

			taxi.r = ci, taxi.c = cj;
			remainedPassengerNum--;
			return true;
		}

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (!InGrid(ni, nj)) continue;
			if (grid[ni][nj] == WALL) continue;
			if (dist[ni][nj] != NOT_VISITED) continue;
			if (dist[ci][cj] + 1 > taxi.remainedGas) continue;

			dist[ni][nj] = dist[ci][cj] + 1;
			q.push({ ni, nj });
		}
	}

	return false;
}

bool Work() {
	if (!FindClosest()) return false;

	if (!Transport()) return false;

	return true;
}

int main() {
	Init();

	while (taxi.remainedGas > 0) {
		if (!Work()) {
			cout << -1;
			return 0;
		}

		if (remainedPassengerNum == 0) {
			cout << taxi.remainedGas;
			return 0;
		}
	}

	if (remainedPassengerNum == 0) cout << taxi.remainedGas;
	else cout << -1;

	return 0;
}