[C/C++] 백준 - 19238번 (스타트 택시 - 시물레이션/BFS)

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

<그림 1>

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>

<그림 3>

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>

<그림 5>

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

<그림 6>

<그림 7>

<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

 

문제를 잘 읽고 시키는대로만 하면 되는 문제였다.

중요한 건 bfs를 통해 계속해서 거리를 최신화 한 후 우선순위에 따라 진행해줘야한다는 것이다.

계속 꺼내고, 집어넣고, 정렬하고 ,, 이 과정을 반복해야하기 때문에 나는 덱을 사용해서 오름차순 정렬한 후 front를 뽑는 방식으로 사용했고, deque에 넣는 value값들은 손님의 위치(x좌표, y좌표), 그 손님의 목적지 좌표(x좌표, y좌표), 택시 위치로부터 손님이 있는 좌표까지의 거리(BFS를 통해 구해야함)의 5가지 정보를 담아두었고, 정렬하는 것도 위에서 하라는대로 해주면 된다.

 

하나 꺼내서 구하고, 시작위치 최신화하고, 다시 다 꺼내서 시작위치로부터 손님이 떨어진 거리 구한 후 다시 다 집어넣고, 정렬하는 방식으로 반복하면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define MAX_SIZE 21
using namespace std;
// 백준 19238번
int N, M, fuel, start_x, start_y;
int graph[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];

deque<pair<pair<pair<int, int>, pair<int, int>>, int>> dq;
queue<pair<int, int>> q;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

bool compare(pair<pair<pair<int, int>, pair<int, int>>, int> lhs, pair<pair<pair<int, int>, pair<int, int>>, int> rhs) {
	if (lhs.second == rhs.second) {
		if (lhs.first.first == rhs.first.first) {
			return lhs.first.second < rhs.first.second;
		}
		else {
			return lhs.first.first < rhs.first.first;
		}
	}
	else {
		return lhs.second < rhs.second;
	}
}

int bfs(int startx, int starty, int x_, int y_) {
	if (startx == x_ && starty == y_) return 0;
	while (!q.empty()) q.pop();
	memset(visited, 0, sizeof(visited));
	
	q.push({ startx, starty }); 
	visited[startx][starty] = 1;

	while (!q.empty()) {
		int nextX, nextY;
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			nextX = cur_x + dx[i];
			nextY = cur_y + dy[i];

			if (nextX < 1 || nextY < 1 || nextX > N || nextY > N) continue;
			if (!visited[nextX][nextY] && graph[nextX][nextY]==0) {
				q.push({ nextX, nextY });
				visited[nextX][nextY] = visited[cur_x][cur_y] + 1;
				if (nextX == x_ && nextY == y_) 
					return visited[nextX][nextY]-1;
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d %d %d", &N, &M, &fuel);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &graph[i][j]);
		}
	}
	scanf("%d %d", &start_x, &start_y);
	for (int i = 0; i < M; i++) {
		int cur_x, cur_y, pos_x, pos_y, len;
		scanf("%d %d %d %d", &cur_x, &cur_y, &pos_x, &pos_y);
		len = bfs(start_x, start_y,cur_x, cur_y);
		if (len == -1) {
			printf("-1");
			return 0;
		}
		dq.push_back(make_pair(make_pair(make_pair(cur_x, cur_y), make_pair(pos_x, pos_y)), len));
	}
	
	int total_fuel = 0;
	while (M--) {
		total_fuel = 0;
		sort(dq.begin(), dq.end(), compare);
		int px = dq.front().first.first.first;
		int py = dq.front().first.first.second;
		int cx = dq.front().first.second.first;
		int cy = dq.front().first.second.second;
		int priority_fuel = dq.front().second;
		total_fuel += priority_fuel;
		int plus = bfs(px, py, cx, cy);
		if (plus == -1) {
			printf("-1");
			return 0;
		}
		total_fuel += plus;
		
		dq.pop_front();

		if (fuel < total_fuel) {
			printf("-1");
			return 0;
		}
		else {
			fuel -= total_fuel;
			fuel += (plus * 2);
		}

		start_x = cx;
		start_y = cy;
		for (int i = 0; i < dq.size(); i++) {
			// 시작지점이 이 구간부터는 cx, cy로 바뀜
			int a, b, c, d, e;
			a = dq.front().first.first.first;
			b = dq.front().first.first.second;
			c = dq.front().first.second.first;
			d = dq.front().first.second.second;
			e = dq.front().second;
			dq.pop_front();
			
			int len_2 = bfs(start_x, start_y, a, b);
			dq.push_back(make_pair(make_pair(make_pair(a, b), make_pair(c, d)), len_2));
		}
	}
	printf("%d\n", fuel);

	return 0;
}