[ 백준 19238 ] 스타트 택시

# 문제링크

www.acmicpc.net/problem/19238

19238번: 스타트 택시

그  아기상어 문제를 풀고 난 뒤부터, 대부분 BFS 문제가 아기상어 문제처럼 보인다. 이것도 BFS로 손님 찾고 visit 초기화, BFS로 목적지 데려다주고 visit 초기화. 이런 식으로 진행된다. 손님을 찾는 BFS에서 손님 번호를 return 해야 하는데, 동시에 손님까지 간 거리도 return 해주고 싶었다. 왜냐면 solve 함수에서 taxi 관련 데이터를 처리하고싶었기 때문이다. 그래서 user_distance 라는 전역 변수를 둬서 거기에 저장해주고, 손님 번호를 리턴했다. 야매 처리방법~! ㅎㅎ

 

함정은 택시와 승객이 같은 위치에 있을 경우이다. 문제에서도 같은 위치에 서있으면 최단거리 0이라고 힌트를 주긴 했다 ㅎ BFS 두개 만드니 코드도 길고 현타도 씨게 온다..

 

# 제출 코드 

 

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int N, M, F;
int map[21][21];
int visited[21][21];
int user_map[21][21];
struct st {
	int uy;
	int ux;
	int dy;
	int dx;
};
st user[401];

struct TAXI {
	int y;
	int x;
	int f;
};
TAXI taxi;
int yd[] = { 1, -1 ,0,0 };
int xd[] = { 0, 0, 1, -1 };

void Input(){
	scanf("%d %d %d", &N, &M, &taxi.f);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	scanf("%d %d", &taxi.y, &taxi.x);

	int uy, ux, dy, dx;
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d %d", &user[i].uy, &user[i].ux, &user[i].dy, &user[i].dx);
		user_map[user[i].uy][user[i].ux] = i; // 사용자 위치 체크맵
	}
}

int user_distance = 0;
int FindUser(int y, int x) {
	vector<pair<int, int>> u;
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = 1;
	int time = 1;

	if (user_map[y][x] != 0) { // 택시와 손님이 같은 위치에 있을 경우
		user_distance = 0;
		int ret = user_map[y][x];
		user_map[y][x] = 0;
		return ret;
	}
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if (time != visited[y][x]) {
			if (u.size()) {
				sort(u.begin(), u.end());
				user_distance = time;
				int ret = user_map[u[0].first][u[0].second];
				user_map[u[0].first][u[0].second] = 0; // 선택된 user 맵에서 지우기 
				return ret;
			}
			time = visited[y][x];
		}
		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];
			if (ny < 1 || ny > N)continue;
			if (nx < 1 || nx > N)continue;
			if (visited[ny][nx] != 0)continue; // 이미 방문
			if (map[ny][nx] == 1)continue; // 벽

			if (user_map[ny][nx] != 0) u.push_back({ ny, nx }); // 손님?
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny,nx });
		}
	}
	return -1;
}

int Move(int dy, int dx) {
	queue <pair<int, int>> q;
	q.push({ taxi.y, taxi.x });
	visited[taxi.y][taxi.x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];

			if (ny < 1 || ny > N)continue; //범위 
			if (nx < 1 || nx > N)continue;
			if (visited[ny][nx] != 0)continue; // 방문했던 곳 
			if (map[ny][nx] == 1)continue; // 벽이당

			if (ny == dy && nx == dx) return visited[y][x]; // 찾았다 목적지!!

			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny, nx });
		}
	}
	return -1;
}

int Solve() {
	for (int i = 0; i < M; i++) {
		user_distance = -1; // 손님까지 거리저장
		memset(visited, 0, sizeof(visited));
		
		int num = FindUser(taxi.y, taxi.x); // 손님 찾아서 번호 리턴 
		if (num == -1) return -1;

		taxi.f -= user_distance;
		taxi.y = user[num].uy;
		taxi.x = user[num].ux;
		if (taxi.f < 0) return -1;

		memset(visited, 0, sizeof(visited));
		int dest = Move(user[num].dy, user[num].dx); // 목적지까지 움직이고 거리 리턴 
		if (dest == -1) return -1;

		if (taxi.f - dest < 0) return -1;
		taxi.f = taxi.f + dest;
		taxi.y = user[num].dy;
		taxi.x = user[num].dx;
	}
	return taxi.f;
}

int main() {
	Input();
	printf("%d", Solve());
}