백준 - 스타트 택시 (19238) [C++]

 이 문제는 bfs를 이용해서 풀었다. 이 문제에서 핵심은 택시가 손님들을 찾는 과정에서 최단거리이며, 만약 거리가 같은 경우 행 번호가 작은, 행 번호도 같다면 열 번호가 작은 손님을 찾는 것이다. 이를 위해 처음에는 bfs의 상하좌우 탐색 순서를 상좌우하 순서로 탐색하고 찾은 경우를 리턴했지만, 이는 정답이 나오지 않았다. 그래서 두 번째 방법으로 일단 bfs를 맵 전체에 대해 돌리고, 손님들의 startY, startX를 기준으로 오름차순 정렬한 배열에 대해 최단거리를 비교하며 손님을 뽑는 형식으로 바꿔 정답을 도출해낼 수 있었다. 이 부분만 잘 해결한다면 나머지는 쉽게 구현 가능한 문제였다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

struct passenger {
	int startY;
	int startX;
	int endY;
	int endX;
};

int N, M;
long long fuel;
int matrix[21][21];
int dy[] = { -1, 0, 0, 1 };
int dx[] = { 0, -1, 1, 0 };
vector<passenger> pass;
vector<vector<int>> dist;

bool inRange(int y, int x) {
	if (1 <= y && y <= N && 1 <= x && x <= N) {
		return true;
	}
	return false;
}

void findPassenger(int startY, int startX) {
	dist = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
	queue<pair<int, int>> q;

	q.push({ startY, startX });
	dist[startY][startX] = 1;

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

		for (int i = 0; i < 4; i++) {
			int ny = present.first + dy[i];
			int nx = present.second + dx[i];

			if (inRange(ny, nx) && dist[ny][nx] == 0 && matrix[ny][nx] != 1) {
				dist[ny][nx] = dist[present.first][present.second] + 1;
				q.push({ ny, nx });
			}
		}
	}
}

int movePassenger(int startY, int startX, int endY, int endX) {
	vector<vector<int>> visited(N + 1, vector<int>(N + 1, 0));
	queue<pair<int, int>> q;

	q.push({ startY, startX });
	visited[startY][startX] = 1;

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

		if (present.first == endY && present.second == endX) {
			return visited[present.first][present.second] - 1;
		}

		for (int i = 0; i < 4; i++) {
			int ny = present.first + dy[i];
			int nx = present.second + dx[i];

			if (inRange(ny, nx) && visited[ny][nx] == 0 && matrix[ny][nx] != 1) {
				visited[ny][nx] = visited[present.first][present.second] + 1;
				q.push({ ny, nx });
			}
		}
	}

	return -1;
}

bool compare(passenger &a, passenger &b) {
	if (a.startY == b.startY) {
		return a.startX < b.startX;
	}
	return a.startY < b.startY;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> fuel;

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			cin >> matrix[y][x];
		}
	}

	int startY, startX;

	cin >> startY >> startX;

	for (int i = 1; i <= M; i++) {
		int sy, sx, ey, ex;

		cin >> sy >> sx >> ey >> ex;

		pass.push_back({ sy, sx, ey, ex });
	}

	sort(pass.begin(), pass.end(), compare);

	for (int i = 0; i < M; i++) {
		// 1. move to passenger
		findPassenger(startY, startX);

		passenger result = { -1, -1, -1, -1 };
		int index = -1;
		int tempDist = 1000000;

		for (int i = 0; i < pass.size(); i++) {
			passenger temp = pass[i];
			int distance = dist[temp.startY][temp.startX];

			if (distance > 0) {
				if (tempDist > distance) {
					tempDist = distance;
					result = temp;
					index = i;
				}
			}
		}

		tempDist--;

		if (index == -1) {
			cout << -1 << '\n';
			return 0;
		}

		pass.erase(pass.begin() + index);

		if (fuel - tempDist < 0) {
			cout << -1 << '\n';
			return 0;
		}
		fuel -= tempDist;

		startY = result.startY;
		startX = result.startX;
		int endY = result.endY;
		int endX = result.endX;

		// 2. move to destination
		tempDist = movePassenger(startY, startX, endY, endX);

		if (tempDist == -1) {
			cout << -1 << '\n';
			return 0;
		}

		if (fuel - tempDist < 0) {
			cout << -1 << '\n';
			return 0;
		}

		fuel += tempDist;
		startY = endY;
		startX = endX;
	}

	cout << fuel << '\n';

	return 0;
}