1)택시가 가장 가까운 승객을 고르고, 2)승객이 정해진 목적지로 가는 거리를 계산해야하는 문제이기 때문에 BFS를 이용한 탐색을 각각 두번 적용하여 문제를 해결하였습니다.
2번의 거리를 BFS로 구했을 때 이는 고정 값으로 택시가 이동해도 손님과 목적지 사이 거리는 변함이 없기 때문에 이는 한 번만 계산을 하면 됩니다. 손님과 목적지 사이의 거리를 불필요하게 계속 구했기 때문에 시간 초과가 발생하기도 했습니다.
택시가 가장 가까운 승객을 고를 때 가장 가까운 거리가 동일하면 행 번호가 작은 승객, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고르게 되어있다. 처음에는 BFS의 큐에 넣을 때 이 순으로 넣어만 주면 먼저 선택되는 손님이 해당 조건에 맞는 손님이라고 착각하였습니다. 하지만 이렇게 BFS 탐색을 하면 잘못된 손님을 선택하게 될 수도 있습니다.
손님는 G1 3행 5열, 손님 G2는 4행 2열에 위치한다고 가정합니다. 표의 숫자는 '(택시와의 거리)-(탐색 순서)'입니다. G1, G2는 모두 거리가 2이지만 문제 조건 상 G1이 선택되어야 하지만 잘못된 BFS 탐색을 구현하면 G2가 선택되게 됩니다. 따라서 문제가 제시한 조건을 그대로 동일한 거리가 여러명이면 먼저 후보자들을 다 구해 놓은 후 행과 열의 우선순위를 따라서 손님을 선택해야합니다.
#include <iostream>
#include <vector>
using namespace std;
int T, N, M;
int gas;
vector<vector<int>> table;
vector<vector<int>> guest;
vector<int> taxi;
int idx = 0;
int valid(int x, int y, vector<vector<int>>& v) {
if(x < 0 || x >= N || y < 0 || y >= N)
return 0;
if(v[x][y] == 0 && table[x][y] == 0) {
v[x][y] = 1;
return 1;
}
else
return 0;
}
int bfs(int a, int b, int c, int d, vector<vector<int>>& q, vector<vector<int>>& visit, int stage) {
if(stage == -1) {
vector<int> p(2, 0);
p[0] = a;
p[1] = b;
q.push_back(p);
visit.resize(N);
for(auto it = visit.begin(); it != visit.end(); it++)
it->resize(N);
visit[a][b] = 1;
return bfs(a, b, c, d, q, visit, stage + 1);
}
else {
int size = q.size();
if(size == 0)
return -1;
for(int i = 0; i < size; i++) {
int x = q[0][0];
int y = q[0][1];
q.erase(q.begin());
if(x == c && y == d)
return stage;
else {
if(valid(x - 1, y, visit)) {
vector<int> t(2, 0);
t[0] = x - 1;
t[1] = y;
q.push_back(t);
}
if(valid(x, y - 1, visit)) {
vector<int> t(2, 0);
t[0] = x;
t[1] = y - 1;
q.push_back(t);
}
if(valid(x, y + 1, visit)) {
vector<int> t(2, 0);
t[0] = x;
t[1] = y + 1;
q.push_back(t);
}
if(valid(x + 1, y, visit)) {
vector<int> t(2, 0);
t[0] = x + 1;
t[1] = y;
q.push_back(t);
}
}
}
return bfs(a, b, c, d, q, visit, stage + 1);
}
}
int taxi_bfs(int a, int b, int c, int d, vector<vector<int>>& q, vector<vector<int>>& visit, int stage, int& idx) {
if(stage == -1) {
vector<int> p(2, 0);
p[0] = a;
p[1] = b;
q.push_back(p);
visit.resize(N);
for(auto it = visit.begin(); it != visit.end(); it++)
it->resize(N);
visit[a][b] = 1;
return taxi_bfs(a, b, c, d, q, visit, stage + 1, idx);
}
else {
int size = q.size();
if(size == 0)
return -1;
for(int i = 0; i < size; i++) {
int x = q[0][0];
int y = q[0][1];
q.erase(q.begin());
for(int j = 0; j < guest.size(); j++) {
if(x == guest[j][0] && y == guest[j][1]) {
if(idx == -1)
idx = j;
else {
int px = guest[idx][0];
int py = guest[idx][1];
int cx = guest[j][0];
int cy = guest[j][1];
if(cx < px) {
idx = j;
}
else if(cx == px) {
if(cy < py)
idx = j;
}
else {}
}
}
}
//else {
if(idx == -1) {
if(valid(x - 1, y, visit)) {
vector<int> t(2, 0);
t[0] = x - 1;
t[1] = y;
q.push_back(t);
}
if(valid(x, y - 1, visit)) {
vector<int> t(2, 0);
t[0] = x;
t[1] = y - 1;
q.push_back(t);
}
if(valid(x, y + 1, visit)) {
vector<int> t(2, 0);
t[0] = x;
t[1] = y + 1;
q.push_back(t);
}
if(valid(x + 1, y, visit)) {
vector<int> t(2, 0);
t[0] = x + 1;
t[1] = y;
q.push_back(t);
}
//}
}
}
if(idx != -1)
return stage;
return taxi_bfs(a, b, c, d, q, visit, stage + 1, idx);
}
}
void solver() {
int i, j;
//int idx = -1;
idx = -1;
int route = 999999999;
int tRoute;
int nog = guest.size();
if(nog == 0)
return;
vector<vector<int>> q;
vector<vector<int>> visit;
route = taxi_bfs(taxi[0], taxi[1], 0, 0, q, visit, -1, idx);
if(idx == -1) {
gas = -1;
return;
}
// go to guest
gas -= route;
if(gas < 0) {
gas = -1;
return;
}
int gx, gy;
tRoute = guest[idx][4];
if(tRoute == -1) {
gas = -1;
return;
}
else {
gas -= tRoute;
if(gas < 0) {
gas = -1;
return;
}
else {
gas += 2 * tRoute;
taxi[0] = guest[idx][2];
taxi[1] = guest[idx][3];
guest.erase(guest.begin() + idx);
}
}
solver();
}
int main() {
T = 1;
int i, j;
for(int tc = 0; tc < T; tc++) {
int tmp;
scanf("%d %d %d", &N, &M, &gas);
table.resize(N);
//taxi.resize(2);
//guest.resize(M);
guest.clear();
for(i = 0; i < N; i++) {
table[i].resize(N);
for(j = 0; j < N; j++) {
scanf("%d", &tmp);
table[i][j] = tmp;
}
}
taxi.resize(2);
scanf("%d", &tmp);
taxi[0] = tmp - 1;
scanf("%d", &tmp);
taxi[1] = tmp - 1;
for(i = 0; i < M; i++) {
vector<int> tv(5,0);
scanf("%d %d %d %d", &tv[0], &tv[1], &tv[2], &tv[3]);
tv[0]--;
tv[1]--;
tv[2]--;
tv[3]--;
tv[4] = 0;
vector<vector<int>> q3;
vector<vector<int>> visit3;
tv[4] = bfs(tv[0], tv[1], tv[2], tv[3], q3, visit3, -1);
guest.push_back(tv);
}
solver();
printf("%d\n", gas);
}
return 0;
}