백준 19238 :스타트택시
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int Map[21][21];
int N, M, K;//맵크기, 목표고객 수 , 연료량
int a, b;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<pair<pair<int, int>, pair<int, int>>> v;
struct info {
int y1, x1, y2, x2;
};
info people[422];
bool cmp(pair<int, pair<int, int>> a , pair<int, pair<int, int>> b) {
if (a.first != b.first) {//행 비교
return a.first < b.first;
}
else if (a.first == b.first && a.second.first != b.second.first) {
return a.second.first < b.second.first;
}
else if(a.first == b.first && a.second.first == b.second.first) {
return a.second.second < b.second.second;
}
}
void go_destination(int r, int c) {
int DstY=0, DstX=0;
for (int i = 0; i < M; i++) {
if (people[i].y1 == r && people[i].x1 == c) {
DstY = people[i].y2, DstX = people[i].x2;
}
}
int temp[21][21];
memset(temp, 0, sizeof(temp));
queue<pair<int, int>>q;
q.push({ r,c });
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny <1 || nx<1 || ny>N || nx > N)continue;
if (Map[ny][nx] == 1)continue;
if (temp[ny][nx] == 0) {
temp[ny][nx] = temp[y][x] + 1;
q.push({ ny,nx });
}
if (ny == DstY && nx == DstX) {
//cout << "현재 잔량" << K << endl;
K -= temp[ny][nx];
//cout << "도착한 뒤 잔량" << K << endl;
if (K < 0) {
K = -1;
return;
}
K += 2*temp[ny][nx];
//cout << "충전량" << 2 * temp[ny][nx] << "현재 K량"<< K << endl;
a = ny, b = nx;
return;
}
}
}
K = -1;
}
void Find_people() {
int temp[21][21];
memset(temp, 0, sizeof(temp));
if (Map[a][b] == 2) {
Map[a][b] = 0;
go_destination(a,b);
return;
}
queue<pair<int, int>>q;
vector<pair<int,pair<int, int>>>v;
q.push({ a, b });
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny <1 || nx<1 || ny>N || nx > N)continue;
if (Map[ny][nx] == 1)continue;
if (temp[ny][nx] == 0) {
temp[ny][nx] = temp[y][x]+1;
q.push({ ny,nx });
}
if (Map[ny][nx] == 2) {
v.push_back({ temp[ny][nx],{ny,nx} });
}
}
}
if (!v.empty()) {
sort(v.begin(), v.end(), cmp);
K -= v[0].first;
//cout << "손님 태우러 가는 동안 따른 양" << K << endl;
if (K <= 0) {
K=-1;
return;
}
Map[v[0].second.first][v[0].second.second] = 0;
go_destination(v[0].second.first, v[0].second.second);
return;
}
K = -1;
}
void simul() {
for (int i = 0; i < M; i++)
Find_people();
}
int main() {
cin >> N >> M >> K;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
cin >> Map[i][j];
cin >> a >> b;
for (int i = 0; i < M; i++) {
cin >> people[i].y1 >> people[i].x1 >> people[i].y2 >> people[i].x2;
int y=people[i].y1, x = people[i].x1;
Map[y][x] = 2;
}
simul();
cout << K;
return 0;
}스타트 택시 성공
| 1 초 (추가 시간 없음) | 512 MB | 19248 | 4187 | 2486 | 19.861% |
문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
<그림 1>
<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.
<그림 2> |
<그림 3> |
<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.
<그림 4> |
<그림 5> |
<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.
<그림 6> |
<그림 7> |
<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
bfs+구현인데, 고려해야하는 조건이 몇 개 있다.
우선
각 손님의 출발지 != 목적지인 것이지 손님1의 출발지 != 손님2의 출발지 && 손님1의 목적지 != 손님2의 목적지인 점을 감안해야한다.
벡터와 큐를 적절히 활용하면 된다.