[Algorithm][C++] BOJ 19238 스타트 택시

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

19238번: 스타트 택시

 

풀이 핵심

1. 최단 거리 --> bfs 문제 (+ 시뮬레이션)

 

2. 벽을 모두 -1로 변경

 

3. 현재 위치 cur_r, cur_c에 저장

 

4. 손님이 있는 곳을 고유한 ID (1, 2, 3, …)로 map에 표시 한다. 손님의 위치와 도착 위치를 target 배열에 표시 한다. 이 때 target 배열의 index는 손님의 ID로 한다.

 

5. findGuest 함수에서 가장 가까운 손님을 탐색 한다. 거리가 같은 손님들이 있을 수 있으므로 탐색한 손님의 수를 cnt 변수로 확인하고 temp라는 배열에 손님들의 정보를 저장한다. Bfs 탐색이 종료되면 temp의 손님 정보를 거리, 행, 열 정보를 기준으로 정렬한다. temp의 가장 맨 앞의 요소의 거리 (현재 시작점에서의) 를 연료에서 뺀다. 이 때 연료가 0보다 작으면 -1을 return 한다. 또한 찾은 손님이 한 명도 없을 경우도 -1을 return 한다. 손님까지 이동하고도 연료가 남아 있다면 손님의 ID를 return 한다.

 

6. findGuest로 부터 return 된 값이 -1이 아닐 경우 손님의 목적지 탐색 함수인 findGoal 함수를 실행한다. findGoal 함수의 전달 인자는 손님의 ID이다. Bfs 탐색을 통해 손님의 위치에서 부터 목적지의 위치까지의 최단 거리를 구한다. 여기서 손님의 목적지에 도달 하지 못하면 -1을 return 한다. 최단 거리를 연료에서 빼고 남은 값이 0보다 작은 경우 -1을 return 한다. 남은 연료가 0 이상이면 손님의 출발지 부터 목적지까지의 최단 거리의 두배를 연료에 충전한다. 그리고 현재 위치 (cur_r, cur_c)를 도착지로 바꾼다. 아직 큐에 pop되지 않은 요소들이 있을 수 있으므로 모두 pop 해준다. map에 표시 된 손님의 ID를 제거 한다.

 

7. findGuest, findGoal을 M번 반복한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, fuel, cur_r, cur_c;
int map[21][21];
struct TARGET { int sr, sc, er, ec; };
TARGET target[20 * 20 + 1];

struct info { int r, c, d, id; };
queue<info> q;

const int dr[] = { 1,-1,0,0 };
const int dc[] = { 0,0,1,-1 };

int comp(info& a, info& b) {
	if (a.d == b.d) {
		if (a.r == b.r) {
			return a.c < b.c;
		}
		return a.r < b.r;
	}
	return a.d < b.d;
}

int findGuest(int sr, int sc) {
	info temp[20 * 20 + 1];
	int ret = -1, cnt = 0;
	int visited[21][21] = { 0, };
	q.push({ sr, sc, 0 });
	visited[sr][sc] = 1;
	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		if (map[cur.r][cur.c]) {
			temp[cnt++] = { cur.r, cur.c, cur.d, map[cur.r][cur.c] };
			continue;
		}
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
			if (map[nr][nc] == -1 || visited[nr][nc])continue;
			q.push({ nr, nc, cur.d + 1 });
			visited[nr][nc] = 1;
		}
	}
	if (cnt) {
		sort(temp, temp + cnt, comp);
		fuel -= temp[0].d;
		if (fuel >= 0) {
			ret = temp[0].id;
		}
	}
	return ret;
}
int findGoal(int idx) {
	int ret = -1;
	int sr = target[idx].sr, sc = target[idx].sc;
	int er = target[idx].er, ec = target[idx].ec;
	bool visited[21][21] = { 0, };
	q.push({ sr,sc,0 });
	visited[sr][sc] = 1;
	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		if (cur.r == er && cur.c == ec) {
			map[sr][sc] = 0;
			ret = cur.d;
			break;
		}
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
			if (map[nr][nc] == -1 || visited[nr][nc])continue;
			q.push({ nr, nc, cur.d + 1 });
			visited[nr][nc] = 1;
		}
	}
	if (ret != -1) {
		fuel -= ret;
		if (fuel >= 0) {
			fuel += (2 * ret);
			cur_r = er, cur_c = ec;
			while (!q.empty()) q.pop();
		}
		else ret = -1;
	}
	return ret;
}

int main() {
	int ret = 0;
	scanf("%d %d %d", &N, &M, &fuel);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			scanf("%d", &map[r][c]);
			if (map[r][c] == 1) map[r][c] = -1;
		}
	}
	scanf("%d %d", &cur_r, &cur_c);
	for (int i = 1; i <= M; i++) {
		int sr, sc, er, ec;
		scanf("%d %d %d %d", &sr, &sc, &er, &ec);
		map[sr][sc] = i;
		target[i] = { sr, sc, er, ec };
	}
	for (int i = 0; i < M; i++) {
		ret = findGuest(cur_r, cur_c);
		if (ret == -1) break;
		ret = findGoal(ret);
		if (ret == -1) break;
	}
	if (ret != -1) ret = fuel;
	printf("%d", ret);
	return 0;
}