BOJ 19238 : 스타트 택시

#BOJ 19238 : 스타트 택시

19238번: 스타트 택시

#풀이

먼저 보드에 벽과 빈칸을 입력을 받는다.

 

그 이후 택시의 시작 좌표와 승객의 시작좌표와 도착좌표를 입력받는다.

 

택시로 부터 가장 가까운 승객을 도착지로 데려다주면서 기름의 남은 량을 구하는 문제이다.

 

나는 일단 택시 좌표, 승객 시작좌표, 승객 도착좌표를 저장하고 

 

구조체를 만들어 승객의 정보를 받았다. 구조체는 승객 좌표, 승객 넘버, 거리까지 저장할 수 있다.

 

BFS를 이용하여 가장 가까운 승객을 구하였다.

(여기서 동일한 거리의 승객이 있으면 행번호가 작고, 열의 번호가 작은 승객부터 우선순위를 준다)

 

이러한 우선순위 때문에 나는 BFS를 택시 좌표에서 부터 거리를 구하여 우선순위 큐에 넣어 우선순위를 생각하여 가장 최소 거리의 승객을 구할 수 있었다.

 

우선순위 구할 때는 거리,행,열 이렇게 cmp 를 만들어서 우선순위를 구할 수 있게 하였다.

 

우선순위 큐에는 승객정보를 저장하는 구조체가 들어간다.

 

예외를 생각해보자!!

 

1. 택시가 승객을 못태울 때 

-택시가 승객까지 갈 수 없다.(벽으로 막힘)

-택시가 승객까지 갈 수 있는 연료가 부족

 

2. 택시가 승객을 도착지까지 못 갈 때

-승객을 태운 택시가 도착지에 갈 수 없다.(벽으로 막힘)

- 승객을 태운 택시가 도착지 갈 연료가 부족

 

3. 택시 시작 좌표에 승객이 있을 때

-맨 처음 시작할 때 승객과 택시가 동일 칸에 있을 수 있음

-승객을 도착지에 데려다 주고 그 도착지에 다른 승객이 있을 수 있음

 

나는 이렇게 생각하고 풀었다...

 

근데 사실 이거 시간초과가 떴다!!

 

모든 승객을 다 태웠는지 확인하려고 suc 배열을 만들어서 1-m까지 승객을 도착지에 데려다 줄 때 마다 돌게 해서 시간초과가 났다...

 

나는 바보야~~~~~~

 

그래서 배열을 만든게 아니라 그냥 간단하게 승객을 도착지에 데려다 줬으면 승객 시작좌표를 -1 로 바꾸고

suc는 그냥 int 변수로 만들어서 개수만 저장하도록 했다~~

 

 

#코드

#include<iostream>
#include<queue>
#include<tuple>
using namespace std;
int n, m, oil;
int board[21][21];
int vis[21][21];
pair<int, int> taxi;
pair<int, int> start[401]; //승객 시작좌표
pair<int, int> end_[401]; // 승객 도착좌표
int suc; // 도착지에 데려다 준 승객 수
int dx[4] = { 1, -1, 0 ,0 };
int dy[4] = { 0,0,1,-1 };
int cur_cli; //현재 태우려고하거나 태운 승객 번호
struct data {
	int x;
	int y;
	int num;
	int dis;
}typedef cli_data;
class cmp {
public:
	bool operator() (cli_data a, cli_data b) { // 가까운 승객 우선순위
		if (a.dis < b.dis) return false; // true b가 앞으로 감
		else if (a.dis == b.dis) {
			if (a.x < b.x) return false;
			else if (a.x == b.x) {
				if (a.y < b.y) return false;
				else return true;
			}
			return true;
		}
		return true;
	}
};
priority_queue<cli_data, vector<cli_data>, cmp>pq;
bool cli_dist() { // 최소 승객 구하기

	for (int i = 1; i <= m; i++) { // 승객과 택시 동일 선상
		if (start[i].first == taxi.first && start[i].second == taxi.second)
		{
			cur_cli = i;
			return 0;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			vis[i][j] = 0;
		}
	}
	while (!pq.empty())
		pq.pop();
	queue<pair<int, int>> q;
	q.push(taxi);
	vis[taxi.first][taxi.second] = 1;

	while (!q.empty()) {
		auto a = q.front(); q.pop();

		for (int j = 0; j < 4; j++) {
			int x = a.first + dx[j];
			int y = a.second + dy[j];

			if (x < 1 || y < 1 || x > n || y > n || board[x][y] == 1 || vis[x][y] != 0)
				continue;

			q.push({ x,y });
			vis[x][y] = vis[a.first][a.second] + 1;
		}
	}

	for (int i = 1; i <= m; i++) { // 택시에서 승객이 길이 다 막혔을 경우 큐에 아무것도 들어가지 않음

		int x = start[i].first;
		int y = start[i].second;
		if (x == -1)
			continue;
		if (vis[x][y] == 0)
			continue;
		pq.push(cli_data{ x,y,i,vis[x][y] - 1 });

	}
	if (pq.empty()) // 큐가 비었다는 건 승객 시작좌표에 택시가 못간다는 뜻
		return 1;
	auto a = pq.top();
	taxi = { a.x, a.y };
	cur_cli = a.num;
	oil = oil - a.dis;
	return 0;
}

int end_dist() { // 목적지 까지 거리 구하기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			vis[i][j] = 0;
		}
	}
	queue<pair<int, int>> q;
	q.push(taxi);
	vis[taxi.first][taxi.second] = 1;
	while (!q.empty()) {
		auto a = q.front(); q.pop();

		for (int j = 0; j < 4; j++) {
			int x = a.first + dx[j];
			int y = a.second + dy[j];

			if (x == end_[cur_cli].first && y == end_[cur_cli].second)
			{
				taxi.first = x;
				taxi.second = y;
				start[cur_cli].first = -1;
				return vis[a.first][a.second];
			}
			if (x < 1 || y < 1 || x > n || y > n || board[x][y] == 1 || vis[x][y] != 0)
				continue;

			q.push({ x,y });
			vis[x][y] = vis[a.first][a.second] + 1;
		}
	}
	return -1; // 반복문을 빠지고 나온거면 BFS를 다 돌아도 도착지를 만나지 못했다는 뜻이므로 택시가 승객을 태우고 도착지에 못간다는 뜻
}

void func() {
	while (1)
	{
		int use_oil = 0;
		if (cli_dist()) {
			cout << -1 << '\n';
			return;
		} // 최소 승객 구하기

		if (oil <= 0) {
			cout << -1 << '\n';
			return;
		}
		use_oil = end_dist();
		if (use_oil == -1) {
			cout << -1 << '\n';
			return;
		}
		oil = oil - use_oil;
		if (oil < 0) {
			cout << -1 << '\n';
			return;
		}
		oil = oil + 2 * use_oil;
		suc++;
		if (suc == m) {
			cout << oil << '\n';
			return;
		}
	}

}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> oil;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> board[i][j];
		}
	}
	int x, y;
	cin >> x >> y;
	taxi = { x,y };

	for (int i = 1; i <= m; i++) {
		int x1, y1;
		cin >> x >> y >> x1 >> y1;
		start[i] = { x,y };
		end_[i] = { x1,y1 };
	}

	func();

}