[백준] 19238 스타트택시

bfs 로 한 좌표에서 다른 좌표까지의 최소거리를 구하는 함수

 

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

19238번: 스타트 택시

 

 

 

1. BFS 로 택시에서 가장 가까운 위치에 있는 승객을 고른다.

- 두명이상의 승객이 같은 거리에 있을 경우, 행/열을 기준으로 선택한다.

- 택시를 승객 위치로 이동시킨다. 

- 승객과 택시의 거리를 연료에서 - 한다.

 

2. 최단 경로 (BFS) 로 승객의 목적지로 이동한다.

- 출발지에서 도착지까지의 거리를 연료에서 - 시킨다.

 

3. 연료를 채운다.

- 2번에서의 출발지에서 도착지까지의 거리의 2배를 연료에 + 한다.

 

각 1, 2, 3 에서 연료가 먼저 떨어지면 중단된다. 모든 손님을 이동시킬 수 없는 경우에도 실패이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct CUS {
	int y, x, target_y, target_x;
};
struct D {
	int y, x, depth;
};

vector <CUS> cus;
int n, m;
int map[21][21];
int x, y, gas;
const int dx[] = {-1, 1, 0 ,0};
const int dy[] = {0, 0, -1, 1};


int drive(int y, int x, int ty, int tx) {
	queue <D> q;
	D d;
	d.y = y; d.x = x; d.depth = 0;
	q.push(d);

	bool visit[21][21] = {false,};

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

		if(y == ty && x == tx) 
			return depth;

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

			if(ny < 0 || nx < 0 || ny >= n || nx >= n || visit[ny][nx]) continue;
			if(map[ny][nx] == 1) continue;
			visit[ny][nx] = true;
			D nd;
			nd.y = ny; nd.x = nx; nd.depth = depth+1;
			q.push(nd);
		}

	}
	return -1;

}

int solve() {
	int customer = m;

	while(customer--) {
		if(gas < 0)
			break;

		int len = 987654321;
		int target_no = 0;
		int cost;

		for(int i=0; i<m; i++) {
			if(cus[i].y == -1)
				continue;
			cost = drive(y, x, cus[i].y, cus[i].x);
			if(cost < 0) {
				customer++;
				break;
			}
			if(len > cost) {
				len = cost;
				target_no = i;
			}
			else if(len == cost) {
				if(cus[i].y == cus[target_no].y) {
					if(cus[i].x < cus[target_no].x)
						target_no = i;
				}
				else if(cus[i].y < cus[target_no].y)
					target_no = i;
			}
		}

		y = cus[target_no].y;
		x = cus[target_no].x;
		gas  -= len;
		if(gas < 0) {
			customer++;
			break;
		}

		cost = drive(y, x, cus[target_no].target_y, cus[target_no].target_x);
		if(cost < 0) {
			customer++;
			break;
		}
		y = cus[target_no].target_y;
		x = cus[target_no].target_x; 
		gas -= cost;
		if(gas < 0) {
			customer++;
			break;
		}

		gas += (cost * 2);

		map[cus[target_no].y][cus[target_no].x] = 0;
		cus[target_no].y = -1;
	}
	if(customer > 0)
		return -1;

	return gas;
}


int main() {
	scanf("%d %d %d", &n, &m, &gas);

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", &map[i][j]);

	scanf("%d %d", &y, &x);
	y--; x--;

	for(int i=0; i<m; i++) {
		CUS tmp;
		scanf("%d %d %d %d", &tmp.y, &tmp.x, &tmp.target_y, &tmp.target_x);
		tmp.y--; tmp.x--; tmp.target_y--; tmp.target_x--;
		map[tmp.y][tmp.x] = i+2;
		cus.push_back(tmp);
	}

	int res = solve();
	printf("%d\n", res);
	return 0;
}