[백준 19238] 스타트 택시

++ 22.11.11 이 방법을 가장 추천함

사이트만 다르고 같은 문제...

https://www.codetree.ai/frequent-problems/autonomous-electric-car/description

코드트리

아래 코드와 확실히 차이나는 실행시간.....

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

19238번: 스타트 택시

#include <cstdio>
#include <queue>
#include <cstring>
int N;	// 격자크기 최대 20 * 20
int M;	// 승객 수 최대 400	
int C;	// 배터리 충전량 최대 500,000

struct _pt
{
	int ex, ey;
}P[400 + 2];	// 인덱스 : 승객번호	// 목적 지점 저장

int cx, cy;		// 전기차의 현재 위치 
int board[20 + 2][20 + 2];	// 도로상황
int pass[20 + 2][20 + 2];	// 승객처음위치, 승객 번호

struct _qt
{
	int x, y;
	int move;
	int batt;
};
std::queue<_qt> Q;
int visited[20 + 2][20 + 2];

void input()
{
	scanf("%d %d %d", &N, &M, &C);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
	scanf("%d %d", &cx, &cy);
	for (int m = 1; m <= M; m++) {
		int x = 0, y = 0, a = 0, b = 0;
		scanf("%d %d %d %d", &x, &y, &a, &b);
		pass[x][y] = m;
		P[m] = { a, b };
	}
	//debug();
}


int get_passenger()	// 승객 고르기	// 현재 위치에서 최단 거리가 가장 짧은 승객을 먼저 태운다 
{
	// init
	memset(visited, -1, sizeof(visited));
	Q = {};

	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	int min_dist = 0x7fffffff; int min_row = 0x7fffffff; int min_col = 0x7fffffff;

	Q.push({ cx, cy, 0, C });
	visited[cx][cy] = 0;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.move > min_dist) break;

		if (data.batt <= 0 && pass[data.x][data.y] == 0) return -1;	// 중간에 연료가 바닥나서 승객 못태우러 감

		if (pass[data.x][data.y] != 0 && data.batt > 0) {	// 승객 태웠고 연료 바닥나지 않음 
			if ((min_dist > data.move) ||
				(min_dist == data.move && min_row > data.x) ||
				(min_dist == data.move && min_row == data.x && min_col > data.y)) {
				min_dist = data.move;
				min_row = data.x;
				min_col = data.y;
			}
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (visited[nx][ny] >= 0) continue;
			if (board[nx][ny] == 1) continue;
			Q.push({ nx, ny, data.move + 1, data.batt - 1 });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
	if (min_dist == 0x7fffffff) return -1;	// 승객 태우지 못함	// 최단거리 갱신안됨 
		 
	int p_num = pass[min_row][min_col];
	pass[min_row][min_col] = 0;
	cx = min_row; 
	cy = min_col;
	C -= min_dist;
	return p_num;
}


int to_goal(int ex, int ey)
{
	// init
	Q = {};
	memset(visited, -1, sizeof(visited));

	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ cx, cy, 0, C });
	visited[cx][cy] = 0;
	
	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.batt < 0 && (data.x != ex || data.y != ey)) return false;

		if (data.x == ex && data.y == ey && data.batt >= 0) {
			C -= data.move;
			C += (data.move * 2);
			cx = data.x;
			cy = data.y;
			return true;
		}


		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (visited[nx][ny] >= 0) continue;
			if (board[nx][ny] == 1) continue;
			Q.push({ nx, ny, data.move + 1, data.batt - 1 });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
}





bool simul()
{
	int cnt = 0;
	while (1) {
		int p_num = get_passenger();
		if (p_num == -1) return false;		// 연료가 없어서 승객을 태우러 가지 못함 
		if (!to_goal(P[p_num].ex, P[p_num].ey)) return false;	// 연료가 없어서 승객을 데려다 주지 못함 
		cnt++;
		if (cnt == M) return true;
	}
}





int main()
{
	input();
	if (simul() == false) printf("%d\n", -1);
	else printf("%d\n", C);
	return 0;
}

1. 승객의 목적지 정보만 구조체에 넣어서 관리하고, pass라는 맵에 승객의 출발좌표와 승객번호를 저장하였다. 

get_passenger 함수로 어떤 승객을 태울지 탐색하다가 pass[data.x][data.y]가 0이 아니면, 즉 해당 칸에 태울 승객이 존재한다면 min_dist, min_row, min_col 값을 갱신한다. 

우선순위에 따라서 승객을 선택해야 하기 때문에 승객을 태웠다고 곧바로 리턴하는 것이 아니라, 해당 거리(min_dist) 상에 있는 모든 승객들을 다 탐색해 보아야 한다. 

그런데 현재 움직인 거리(data.move) 가 min_dist 보다 커지면 어차피 최단 거리에 있는 승객이 아니므로 while 루프를 빠져나온다. 

 

2. BFS 탐색을 통해 구한 min 값들로 전기차 정보를 갱신하고 (백준에서는 택시정보 ㅋㅋ..) 만약 손님을 태웠을 경우 pass[min_row][min_col] 위치에 저장되어 있던 숫자를 리턴한다. 해당 숫자는 현재 태운 승객의 번호이다. (input 받을 때 부여함)

 

3. 또 다른 BFS 함수인 to_goal은 출발지와 목적지가 있을 때, 목적지 까지의 최단 거리를 반환해주는 전형적인 BFS 탐색을 진행한다. 

 

4. 1, 3번을 진행하면서 주의해야 했던 것은, 이동 중 전기차의 배터리가 모두 소모되면 바로 이동을 중지한다는 것이다. 따라서 루프를 돌 때 승객의 위치(get_passenger 함수) 가 아닌데 data.batt가 0이되는 경우이거나, 목적지(to_goal 함수)가 아닌데 data.batt가 0 미만이되는 경우라면 -1를 리턴하여 승객을 태우거나 데려다 줄 수 없음을 표시했다. 

이때 승객을 목적지에 데려다주는 동시에 배터리가 0이되는 경우는 이동을 중지하지 않는다고 하였으므로, 부등호를 신경써주도록 하자.. 

 

---

++ 22.10.26 FIFO 큐를 사용하였지만 BFS를 여러번 돌린 풀이.. (실행시간 많이나옴. 비효율적, 하지만 풀리긴 함)

#include <cstdio>
#include <queue>
#include <algorithm>
int N, M, K;
int board[20 + 2][20 + 2];
int tx, ty;

struct _pt
{
	int sx, sy;
	int ex, ey;
	bool arr = false;
};
_pt Pass[400 + 2];	// (승객 출발지) (승객 목적지)


struct _qt
{
	int x, y;
};

std::queue<_qt> Q;
int visited[20 + 2][20 + 2];

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &board[i][j]);
		}
	}

	scanf("%d %d", &tx, &ty);

	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d %d", &Pass[i].sx, &Pass[i].sy, &Pass[i].ex, &Pass[i].ey);
	}
}


int get_dist(int pid)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	Q = {};
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), -1);

	Q.push({ tx, ty});
	visited[tx][ty] = 0;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.x == Pass[pid].sx && data.y == Pass[pid].sy) return visited[data.x][data.y];

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (visited[nx][ny] > 0 ) continue;
			if (board[nx][ny] == 1) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
	return -1;
}




int get_passenger()
{
	int min_dist = 0x7fffffff;
	int min_row = 0x7fffffff;
	int min_col = 0x7fffffff;
	int passenger = -1;

	for (int i = 1; i <= M; i++) {
		if (Pass[i].arr == true) continue;
		int dist = get_dist(i);
		if (dist == -1) continue;		// 손님 못태웠음

		if ((dist < min_dist) ||
			(dist == min_dist && Pass[i].sx < min_row) ||
			(dist == min_dist && Pass[i].sx == min_row && Pass[i].sy < min_col)) {
			min_dist = dist;
			min_row = Pass[i].sx;
			min_col = Pass[i].sy;
			passenger = i;
		}
	}

	if (K - min_dist <= 0) return -1;	// 이동 도중 연료 바닥남
	if (passenger == -1) return -1;		// 손님 못태웠음
	K -= min_dist;
	tx = min_row;
	ty = min_col;
	return passenger;
}



bool go_goal(int pid)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	Q = {};
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), -1);

	Q.push({ tx, ty });
	visited[tx][ty] = 0;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.x == Pass[pid].ex && data.y == Pass[pid].ey && K >= visited[data.x][data.y]) {
			Pass[pid].arr = true;
			tx = data.x;
			ty = data.y;
			K = (K - visited[data.x][data.y]) + (2 * visited[data.x][data.y]);
			return true;
		}

		if (K < visited[data.x][data.y]) {	// 이동 도중 연료 바닥남
			if (data.x != Pass[pid].ex || data.y != Pass[pid].ey) return false;
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (visited[nx][ny] > 0) continue;
			if (board[nx][ny] == 1) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
	return false;
}



bool chk_passenger()
{
	for (int i = 1; i <= M; i++) {
		if (Pass[i].arr == false) return false;
	}
	return true;
}



int simulation()
{
	while (1) {
		int pid = get_passenger();
		if (pid == -1) return -1;		// 연료가 없어서 손님 못태우러 감

		if (!go_goal(pid)) return -1;	// 연료가 없어서 손님 못데려다 줌 

		if (chk_passenger()) return K;	// 손님 다 데려다 줬으면 남은 연료의 양 리턴
	}
}


int main()
{
	input();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}

이 문제도 아기상어랑 비슷하게.. 승객을 태울 때 우선순위가 있기는 하지만, 우선순위 큐가 아니라 FIFO 큐로도 구현 가능하다. 대신에 BFS를 여러번 돌려야해서 보다시피 실행시간이 좀 많이 나옴..

---

PQ를 사용한 이전풀이...

#include <cstdio>
#include <queue>
#include <vector>

int N, M, G;	// 맵 크기, 손님, 연료양 
int vx, vy;		// 택시위치 
int tx, ty;		// 택시위치 
int taxi_map[20 + 2][20 + 2];
int chk[20 + 2][20 + 2];

struct _st		// 승객 정보 저장용 
{
	int x;
	int y;
};

struct _qt		// 큐용
{
	int x;
	int y;
	int move;
};

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


struct COMP	// 거리가 가까운 승객을 고른다 
{
	bool operator()(_qt &a, _qt &b) {
		if (a.move == b.move && a.x == b.x) return a.y > b.y;
		if (a.move == b.move) return a.x > b.x;
		return a.move > b.move;
	}
};

std::priority_queue<_qt, std::vector<_qt>, COMP> PQ;	//	손님용 
std::queue<_qt> Q;	// 목적지용

std::vector<_st> Visitor[400 + 2][400 + 2];		// [출][발] = 도착

void input()
{
	scanf("%d %d %d", &N, &M, &G);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &taxi_map[i][j]);
		}
	}
	scanf("%d %d", &tx, &ty);
	for (int m = 0; m < M; m++) {
		int sx = 0, sy = 0, ex = 0, ey = 0;
		scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
		Visitor[sx][sy].push_back({ ex, ey });	// 승객의 출발지 - 목적지 페어로 관리 
		taxi_map[sx][sy] = 2;						// 손님이 있는 곳 (출발지 == 2)로 설정
	}
}


int get_visitor(int gas)
{
	std::fill(&chk[0][0], &chk[0][0] + sizeof(chk) / sizeof(int), -1);	// 각 손님의 최단거리 구해야 하므로 
	bool ride = false;	// 승객을 태웠는지 안태웠는지 체크
	PQ = {};
	PQ.push({ tx, ty, 0 });		// 초기 택시 위치 
	chk[tx][ty] = 0;


	while (!PQ.empty()) {
		_qt data = PQ.top();
		PQ.pop();

		if (ride == false && gas - data.move <= 0) return -1;	// 승객도 안태웠는데 연료 없을 때 

		// 승객이 있는 곳에 도달했을 때 
		if (ride == false && taxi_map[data.x][data.y] == 2) {
			vx = data.x, vy = data.y;	// 손님 위치 저장 
			taxi_map[vx][vy] = 0;
			return chk[vx][vy];
		}


		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;		// 좌표 유효성 먼저 검사하기 
			if (chk[nx][ny] != -1) continue;		// 이미 방문한 곳이라면 스루 
			if (taxi_map[nx][ny] == 1) continue;	// 벽이면 스루
			chk[nx][ny] = data.move + 1;
			PQ.push({ nx, ny, chk[nx][ny] });
		}
	}
	return -1;
}



int get_target(int gas)
{
	std::fill(&chk[0][0], &chk[0][0] + sizeof(chk) / sizeof(int), -1);	// 목적지까지의 최단거리 구한다 
	bool arrive = false;
	Q = {};
	Q.push({ vx, vy, 0 });		// 초기 택시 위치는 승객을 태운 위치
	chk[vx][vy] = 0;

	while (!Q.empty()) {
		_qt data = Q.front();
		//printf("[dq]%d %d %d\n", Q.front());
		Q.pop();

		if (arrive == false && gas - data.move < 0) return -1;	// 아직 목적지까지 도달하지 않았는데 연료 없을 때 
		if (data.x == Visitor[vx][vy][0].x && data.y == Visitor[vx][vy][0].y) {
			arrive = true;
			tx = data.x, ty = data.y;	// 택시 위치를 손님의 도착점으로 갱신
			return gas + chk[tx][ty];
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;		// 좌표 유효성 먼저 검사하기 
			if (chk[nx][ny] != -1) continue;		// 이미 방문한 곳이라면 스루 
			if (taxi_map[nx][ny] == 1) continue;	// 벽이면 스루
			chk[nx][ny] = data.move + 1;
			Q.push({ nx, ny, chk[nx][ny] });
			//printf("[eq]%d %d %d\n", nx, ny, chk[nx][ny]);
		}
	}
	return -1;
}





void simul()
{
	while (M) {					// 손님 M명이므로 BFS M번 
		int p_remain = get_visitor(G);
		if (p_remain == -1) {
			printf("%d\n", -1);
			return;
		}
		G -= p_remain;			// 남아있는 연료 갱신

		int t_remain = get_target(G);
		if (t_remain == -1) {		// remain이 0일수도 있으므로 
			printf("%d\n", -1);
			return;
		}
		G = t_remain;			// 남아있는 연료 갱신
		M--;
	}
	printf("%d\n", G);
}



int main()
{
	input();
	simul();
	return 0;
}

원래 BFS 한 개 쓰고 싶었는데 머가리의 한계로 인해 함수를 두 개 사용했다. 

 

 

// get_visitor( ) 함수

택시를 태울 승객을 고르는 함수이다. 

아기상어 풀면서 했던 나와의 약속을 지켰다 ! 특정한 조건을 기준으로 큐에서 데이터를 빼내야 할 때 반드시 "우선순위 큐" 를 쓰는 것이다. 문제에서 승객을 고르는 기준은 다음과 같다. 

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 
그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 
그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.

그래서 뒤도 안돌아보고 승객을 고를 자료구조로 PQ를 선택했다. 

 

그리고 상태를 발전시킬 때 마다 남아있는 연료를 확인하여, 그것이 0보다 작거나 같으면 -1을 리턴하면서 바로 함수를 빠져나오게끔 설계하였다. 

 

또한 택시가 승객을 태웠다면, 데이터를 입력받을 때 2로 표시해두었던 손님의 출발점을 0으로 갱신해주었다. 해당 위치의 손님을 태웠기 때문에 또 다시 태우러 방문하지 않기 위함이다. 

 

 

// get_target( ) 함수

승객을 목적지 까지 최단 경로로 데려다 주기 위한 함수이다. 

여기서는 PQ를 쓸 필요가 없다. 그래서 해당 함수용 큐를 한 개 더 선언하였다. 

이때 처음 택시의 위치는 승객을 태운 위치이다. 따라서 get_visitor 함수를 실행하면서 저장했던 승객의 위치 (vx, vy) 를 초기 상태로 큐에 삽입하였다. 

 

해당 함수에서 중요한 점은 다음 두 가지이다. 

1. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다. 

=> get_visitor함수에서는 남아있는 연료가 0보다 작거나 같을 때 -1을 리턴했지만, 1번의 조건 때문에 이때는 등호를 빼주어야 한다. 

 

2 - 1. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단 거리는 0이다. 

2 - 2. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다. 

=> 이전 승객의 목적지가 다음 승객의 출발지가 될 수 있음을 주의해야 한다. 나는 이 조건을 놓치고 해당 함수에서도 승객을 목적지까지 데려다주었을 때 taxi_map[tx][ty] = 0; 이런식으로 맵을 0으로 초기화해주었다. 이러면 승객의 출발지에 대한 정보도 날아가기 때문에 이 과정은 절대 추가해서는 안된다.