19238. 스타트 택시

8% , 82% 에서 두번 막히고 적는 확인할 점들

1. 사람이 서있는 곳도 택시는 지날 수 있다. [ 손님을 택시에 태워서 도착지로 가능 경우,]

2. 동일한 거리가 있을 경우, 행/렬 크기로 우선순위 설정

3. 도착지가 다른 사람의 출발지가 될 수 있다. => 출발지가 적혀있는 배열에 도착지를 표시할 경우, 데이터가 사라질 수 있다.

4. 도착지로 갈 수 없는 경우가 있다. 

 

 

#include<iostream>
#include <vector>
#include<stdlib.h>
#include<algorithm>
#include <queue>
using namespace std;
typedef struct value {
	int i;
	int j;
	long long f;

};
typedef struct person {
	int si;
	int sj;
	int ei;
	int ej;
};

value taxi ;
vector<person> p;
int n, m, k;
int map[25][25] = { 0 };
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
int cm[25][25];
value bfs_t() { 
	queue<value> qu; //f = 거리
	qu.push({ taxi.i, taxi.j, 0});
	qu.push({ -1,-1,-1 });
	vector<value> answer;
	int check[25][25] = { 0 };
	check[taxi.i][taxi.j] = 1;
	if (cm[qu.front().i][qu.front().j] >= 2)
		return { taxi.i, taxi.j,0 };
	while (!qu.empty()) {
		value a = qu.front();
		qu.pop();
		if (a.i == -1) {
			if (!answer.empty()) {
				value min = answer[0];
				for (int i = 1; i < answer.size(); i++) {
					if (answer[i].i < min.i) {
						min = answer[i];
					}
					else if (answer[i].i == min.i) {
						if (answer[i].j < min.j)
							min = answer[i];
					}
				}
				return min;
			}
			qu.push({ -1,-1,-1 });
			a = qu.front();
			qu.pop();
		}
		int i = a.i;
		int j = a.j;
		int d = a.f;
		
		for (int k = 0; k < 4; k++) {
			if (i + dx[k] > 0 && i + dx[k] <= n && j + dy[k] > 0 && j + dy[k] <= n) {
				
				if (cm[i + dx[k]][j + dy[k]] >= 2) {
					check[i + dx[k]][j + dy[k]] = 1;
					answer.push_back({ i + dx[k],j + dy[k],d + 1 });
				}
				else if (map[i + dx[k]][j + dy[k]] == 0&& check[i + dx[k]][j + dy[k]] == 0) {
					check[i + dx[k]][j + dy[k]] = 1;
					qu.push({ i + dx[k],j + dy[k],d + 1 });
				}
				
			}
		}
	}
	return { -1,-1,-1 };
}

value bfs_p(int ii, int jj) {
	queue<value> qu; //f = 거리
	qu.push({ taxi.i, taxi.j, 0 });
	int check[25][25] = { 0 };
	check[taxi.i][taxi.j] = 1;
	if (taxi.i == ii && taxi.j == jj) 
		return { taxi.i, taxi.j,0 };
	while (!qu.empty()) {
		value a = qu.front();
		qu.pop();
		int i = a.i;
		int j = a.j;
		int d = a.f;

		for (int k = 0; k < 4; k++) {
			if (i + dx[k] > 0 && i + dx[k] <= n && j + dy[k] > 0 && j + dy[k] <= n) {
				if (i + dx[k] == ii && j + dy[k] == jj) {
					return { i + dx[k],j + dy[k],d + 1 };
				}
				if (map[i + dx[k]][j + dy[k]] == 0&& check[i + dx[k]][j + dy[k]] ==0) {
					check[i + dx[k]][j + dy[k]] = 1;
					qu.push({ i + dx[k],j + dy[k],d + 1 });
				}
				
			}
		}
	}
	return { -1,-1,-1 };
}

int main() {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);


	cin >> n >> m >> k;
	

	//vector<vector<int>> map;
	//vector<int> a;
	//map.push_back(a);
	for (int i = 1; i <= n; i++) {
		//vector<int> a;
		//map.push_back(a);
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	int i, j, f;
	cin >> i >> j;
	taxi.i = i;
	taxi.j = j;
	taxi.f = k;
	p.push_back({ 0,0,0,0 });
	p.push_back({ 0,0,0,0 });
	for (int i = 0; i < m; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		p.push_back({ a, b, c, d });
		cm[a][b] = p.size() - 1;
	}

	int sig = 0;
	for (int q = 0;  q < m; q++) {
		if (taxi.f <= 0) {
			sig = 1;
			break;
		}

		value a=bfs_t();
		int i = a.i;
		int j = a.j;
		int d = a.f;
		int pe = 0;
		if (i == -1) {
			sig = 1;
			break;
		}
		if (taxi.f - d <= 0) {
			sig = 1;
			break;
		}
		taxi.i = i;
		taxi.j = j;
		taxi.f -= d;
		p[cm[i][j]].si = -1;
		pe = cm[i][j];//몇번재 사람인지
		cm[i][j] = 0;//사람을 태웠다.
	
		int ei = p[pe].ei;
		int ej = p[pe].ej;
		a = bfs_p(ei,ej);
		if (a.i == -1) {
			sig = 1;
			break;
		}
		i = a.i;
		j = a.j;
		d = a.f;
		if (taxi.f - d <= 0) {
			sig = 1;
			break;
		}
		taxi.i = ei;
		taxi.j = ej;
		taxi.f -= d;
		taxi.f += (d * 2);
	}
	if (sig)
		cout << -1;
	else
		cout << taxi.f;

	return 0;
}

 

 

www.acmicpc.net/problem/19238

19238번: 스타트 택시