19238 스타트택시

19238 스타트택시 > 2036KB, 584ms

메모리는 보통, 속도는 느린편 -> 사람 찾을 때 BFS 한 번만 하면 됨!

• 간단한 로직
  • BFS 기본
  • 태울 사람이 남아있는지 체크하고 -> 고르고 -> 태우고
  • 태울 사람이 남아있는지 체크 : 태운 사람을 move_people로 저장하고 태울때마다 move_people++, move_people이 M(승객 수)와 같아지면 종료
  • 고르고 : queue에 담아둔 사람을 한명씩 bfs로 거리 체크함. 이때 태울 사람은 있지만 태우러 갈 수 없는 경우(사방이 벽)에는 flag를 써서 확인. 사람을 고르면 move_people++해주고 차량이동 및 연료 감소시킴
  • 태우고 : 고른 사람의 출발지와 목적지만 bfs하고 차량 옮기고 연료 빼주고 연료 남아있으면 연료 충전
• 주의 사항 
  • 0차 : 종료 조건 고려안하고 로직 짬, 1차 : 연료만 고려하고 사람 고려 안함, 2차 : 모든 손님 이동 불가 고려 안함,
  • 4차 : 택시와 손님이 같은 곳에 서있을 때 고려 안함
  • y & x 주의하기!

#include <iostream>
#include <queue>

#define MAX 20
using namespace std;

typedef struct people {
	bool finish = false;
	int start_y;
	int start_x;
	int dest_y;
	int dest_x;
}PEOPLE;

typedef struct bfs_struct {
	int y, x, route = 0;
}BFS_STRUCT;

int N, M, map[MAX + 1][MAX + 1] = {};
long long int fuel;
int car_y, car_x;
PEOPLE pe_arr[MAX * MAX] = {};
int move_people = 0;

void input() {
	cin >> N >> M >> fuel;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];

	cin >> car_y >> car_x;

	for (int i = 0; i < M; i++)
		cin >> pe_arr[i].start_y >> pe_arr[i].start_x >> pe_arr[i].dest_y >> pe_arr[i].dest_x;	
}

int go_y, go_x, pe_index, shortest_route;

int BFS(int index, bool mode) { // mode false : start, true : dest;
	bool flag = false;
	int goal_y, goal_x;
	int result = 1000000;
	bool visited[MAX + 1][MAX + 1] = {};
	int dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 };

	if (!mode) {
		goal_y = pe_arr[index].start_y;
		goal_x = pe_arr[index].start_x;
	}
	else {
		goal_y = pe_arr[index].dest_y;
		goal_x = pe_arr[index].dest_x;
	}

	queue<BFS_STRUCT> q;
	q.push({ car_y, car_x, 0 });
	visited[car_y][car_x] = true;

	if (car_y == goal_y && car_x == goal_x) return 0;
	while (!q.empty()) {
		int now_y = q.front().y, now_x = q.front().x, now_route = q.front().route; q.pop();

		for (int i = 0; i < 4; i++) {
			int new_y = now_y + dy[i], new_x = now_x + dx[i];
			if (new_y > N || new_x > N || new_y <= 0 || new_x <= 0
				|| visited[new_y][new_x] || map[new_y][new_x] == 1) continue;
			if (new_y == goal_y && new_x == goal_x && result > now_route + 1) {
				result = now_route + 1;
				flag = true;
				continue;
			}

			q.push({ new_y, new_x, now_route + 1 });
			visited[new_y][new_x] = true;
		}
	}

	if (!flag) return -1;
	return result;
}

bool choose() {
	shortest_route = 1000000;
	bool flag = false;
	for (int i = 0; i < M; i++) {
		if (pe_arr[i].finish) continue;

		int bfs_result = BFS(i, false);
		if (bfs_result < 0) continue;
		flag = true;

		if (bfs_result < shortest_route) {
			pe_index = i; go_y = pe_arr[i].start_y; go_x = pe_arr[i].start_x; shortest_route = bfs_result;
		}
		else if (bfs_result == shortest_route) {
			if (pe_arr[i].start_y < go_y) {
				pe_index = i; go_y = pe_arr[i].start_y; go_x = pe_arr[i].start_x; shortest_route = bfs_result;
			} else if (pe_arr[i].start_y == go_y) {
				if (pe_arr[i].start_x < go_x) {
					pe_index = i; go_y = pe_arr[i].start_y; go_x = pe_arr[i].start_x; shortest_route = bfs_result;
				}
			}
		}
	}

	if (!flag) return false;

	move_people++;
	car_y = go_y;
	car_x = go_x;
	fuel -= shortest_route;
	pe_arr[pe_index].finish = true;

	if (fuel < 0) return false;

	return true;
}

bool go() {
	int bfs_result = BFS(pe_index, true);
	if (bfs_result < 0) return false;

	car_y = pe_arr[pe_index].dest_y;
	car_x = pe_arr[pe_index].dest_x;
	fuel -= bfs_result;
	if (fuel >= 0) fuel += (bfs_result * 2);
	else return false;

	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();

	while (move_people < M) {
		if (!choose()) {
			cout << -1;
			return 0;
		}

		if (!go()) {
			cout << -1;
			return 0;
		}
	}
	cout << fuel;
	return 0;
}