문제
$N\times N$정사각형 격자판이 있다. 각 칸은 이동가능한 칸이거나 벽이다. 또 $M$명의 택시 승객이 있는데, 각 승객은 현재 위치와 목적지를 갖는다. 택시는 벽이 아닌 상하좌우 칸으로 이동할 수 있으며, 초기 연료의 양도 주어진다.
택시를 운전해서 가장 가까운 승객(여럿이라면 그 중 행/열번호가 가장 작은)을 목적지로 태워주는 것을 반복한다고 하자. 택시는 한 칸 움직일 때마다 연료를 1 소모하며, 어떤 승객을 성공적으로 태워주었다면 승객을 태운 상태로 이동한 거리의 두 배 만큼 연료를 회복한다.
모든 승객을 태워다 줄 수 있는지, 가능하다면 마지막에 남는 연료는 몇인지 구하는 문제이다.
접근
어떤 승객이 존재하는지, 또 존재한다면 목적지는 어디인지 구하기 위하여 map<pair<int,int>,pair<int,int>>을 사용하였다. 그리고 택시가 한 명의 승객을 성공적으로 태우는 부분을 taxi()함수로 구현하고, 이것이 실패할 때까지 무한 루프가 돌도록 하였다.
다음 태울 승객을 구하려면 각 승객까지의 위치를 알아야 한다. 이를 위해 먼저 BFS를 이용하여 현재 택시의 위치를 기준으로 모든 칸까지의 거리를 구하는 void get_all_distance()를 구현하였다. 이 함수를 호출 한 이후에, 승객 정보를 담은 map을 순회하면서 가장 가까운 승객을 찾는다. 태울 승객을 찾았다면 그 승객을 태우고, 목적지로 이동한다. 이렇듯 기본적인 알고리즘은 간단하고, 사이 사이에 어떤 경우에 성공적으로 승객을 운송할 수 없는지 생각하여 처리해주면 된다.
주의할 점
승객을 성공적으로 나를 수 없는 경우를 꼼꼼히 생각해보아야 한다.
- 벽에 막혀서 다음 승객이 있는 곳까지 갈 수 없는 경우
- 다음 승객이 있는 곳까지 갈 연료가 없는 경우
- 비슷하게, 벽에 막혀서 목적지까지 갈 수 없는 경우
- 연료가 없어서 목적지까지 갈 수 없는 경우
등이 있을 것이다. 나는 80% 언저리에서 틀렸습니다를 한 번 받았는데, 승객이 벽에 막혀서 갈 수 없는 곳을 목적지로 설정한 경우를 제대로 처리해주지 않아서였다.
Code
링크#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int N, M, F;
int x, y;
int board[20][20] = {0};
int distance_board[20][20];
int MAX_DIST = 1000;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
map<pair<int, int>, pair<int, int>> customer;
void get_all_distance() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
distance_board[i][j] = MAX_DIST;
}
}
deque<pair<int, int>> Q;
Q.push_back(make_pair(x, y));
distance_board[x][y] = 0;
while (Q.size() != 0) {
int row, col;
tie(row, col) = Q.front();
Q.pop_front();
for (int d = 0; d < 4; d++) {
int nrow = row + dx[d];
int ncol = col + dy[d];
int ndist = distance_board[row][col] + 1;
if (0 <= nrow && nrow < N && 0 <= ncol && ncol < N && board[nrow][ncol] != 1 && ndist < distance_board[nrow][ncol]) {
distance_board[nrow][ncol] = ndist;
Q.push_back(make_pair(nrow, ncol));
}
}
}
}
bool taxi() {
// first, do bfs to find next target customer.
get_all_distance();
pair<int, int> nearest_customer;
int nearest_distance = MAX_DIST;
for (auto iter : customer) {
pair<int, int> key = iter.first;
if (distance_board[key.first][key.second] < nearest_distance) {
nearest_distance = distance_board[key.first][key.second];
nearest_customer = key;
}
}
// stop iteration if customer was not found
if (nearest_distance == MAX_DIST) {
if (customer.size() != 0) {
F = -1;
}
return false;
}
// stop iteration if fuel is low
if (F < nearest_distance) {
F = -1;
return false;
}
// move taxi to customer position
F -= nearest_distance;
x = nearest_customer.first;
y = nearest_customer.second;
// move taxi to goal.
get_all_distance();
pair<int, int> goal = customer[nearest_customer];
x = goal.first;
y = goal.second;
int used = distance_board[x][y];
customer.erase(nearest_customer);
if (used == MAX_DIST || F < used) {
F = -1;
return false;
}
// refill fuel twice.
F += used;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// get input
cin >> N >> M >> F;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
cin >> x >> y;
x--, y--; // zero-based index
for (int i = 0; i < M; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
customer[make_pair(a - 1, b - 1)] = make_pair(c - 1, d - 1);
}
while (taxi()) {
}
cout << F;
return 0;
}
여담
이번에는 map을 사용하는 법을 공부해보게 되었다. 사실 꼭 map을 쓸필요는 없는것 같은데, Python에는 없는 구조라 맛을 보았다. 뭐…그냥 신기한 것 같다.
