문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.
<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.
<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.
<그림 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을 출력한다.
풀이
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define MAX 21
//택시와 가장 가까운 승객 구하기 위한 함수 (우선순위큐 비교함수는 리턴값을 반대로 짜야됨)
struct cmp {
bool operator()(vector<int> a, vector<int> b) {
if (a[0] < b[0])
return false;
//택시와의 거리가 같을 경우 행과 열을 비교함
else if (a[0] == b[0]) {
if (a[1] < b[1])
return false;
else if (a[1] == b[1])
return a[2] >= b[2];
else
return true;
}
else
return true;
}
};
// 택시 연료, 탐색할 승객의 인덱스를 저장하는 변수
int N, M, taxi_fuel, cust_idx;
//승객위치에서 택시까지의 거리 저장 (거리, 승객_x, 승객_y, 승객번호)
priority_queue<vector<int>, vector<vector<int>>, cmp> dist;
//승객 출발지, 목적지 저장 (출_x, 출_y, 목_x, 목_y)
vector<vector<int>> cust_info;
//지도 정보
int MAP[MAX][MAX];
//방문 정보
int visited[MAX][MAX];
//지도 탐색할때 출발지점, 목적지점 저장 배열
int start[2], End[2];
//지도내에서 상하좌우로 이동하기 위한 변수
int loc[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
//승객과 택시들 간 거리 계산 or 승객 태우고 목적지 이동한 거리 계산
// => flag가 true이면 승객-택시 계산, false이면 승객태워서 목적지 이동
bool calc_dist(bool flag, int index) {
//이동할 지점 저장 (초기에는 각 승객의 출발지 저장)
queue<pair<int, int>> need_visit;
need_visit.push({ start[0], start[1] });
while (!need_visit.empty()) {
int x = need_visit.front().first;
int y = need_visit.front().second;
need_visit.pop();
//이동 중에 연료가 떨어질 경우 false 반환
if (taxi_fuel < visited[x][y])
return false;
//목적지에 도착했을 경우
if (x == End[0] && y == End[1]) {
//승객과 택시 간의 거리를 계산하는 경우
if (flag) {
//dist에 거리, 출발지점, 인덱스를 저장
dist.push({ visited[x][y], start[0], start[1], index });
return true;
}
//승객 태우고 목적지 이동했을때 거리 계산하는 경우
else {
//연료에 이동한 거리 더함(-이동거리 + 이동거리*2 => +이동거리)
taxi_fuel += visited[x][y];
return true;
}
}
//현재지점에서 상하좌우로 이동하며 목적지점 찾기
for (int i = 0; i < 4; i++) {
int n_x = x + loc[i][0];
int n_y = y + loc[i][1];
if (n_x < 1 || n_x > N || n_y < 1 || n_y > N)
continue;
if (MAP[n_x][n_y] == 1 || visited[n_x][n_y] != -1)
continue;
//탐색가능한 지점일 경우 이전지점의 visited값의 1을 더함
visited[n_x][n_y] = visited[x][y] + 1;
//다음 탐색 지점 저장
need_visit.push({ n_x, n_y });
}
}
//목적지에 도달할 수 없는 경우 false 반환
return false;
}
void reset_visited() {
//visited배열 -1로 초기화
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
visited[i][j] = -1;
}
}
//시작지점은 0으로 변경
visited[start[0]][start[1]] = 0;
}
int main() {
bool flag;
cin >> N >> M >> taxi_fuel;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> MAP[i][j];
}
}
//택시의 현재위치를 도착지점으로 저장
cin >> End[0] >> End[1];
for (int i = 0; i < M; i++) {
int s_x, s_y, e_x, e_y;
cin >> s_x >> s_y >> e_x >> e_y;
//승객정보 벡터에 출발지점 x,y좌표와 도착지점 x,y좌표 삽입
cust_info.push_back({ s_x, s_y, e_x, e_y });
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < cust_info.size(); j++) {
//각 승객의 출발지점을 출발지로 설정
start[0] = cust_info[j][0];
start[1] = cust_info[j][1];
//visited배열 초기화, 시작점만 0으로 표시
reset_visited();
//승객과 택시까지의 최단 거리 계산
flag = calc_dist(true, j);
}
//택시를 탈 수 있는 승객이 없으면 반복문 종료
if (dist.empty()) {
taxi_fuel = -1;
break;
}
//이동거리만큼 택시 연료에서 뺌
taxi_fuel -= dist.top().front();
for (int i = 0; i < 2; i++) {
//탐색 승객의 출발지와 목적지를 각 변수에 넣음
start[i] = cust_info[dist.top().back()][i];
End[i] = cust_info[dist.top().back()][i + 2];
}
//해당 승객은 승객정보에서 지움
cust_info.erase(cust_info.begin() + dist.top().back());
//이동정보 초기화
while (!dist.empty())
dist.pop();
//visited배열 초기화
reset_visited();
//승객 출발지에서 목적지까지 이동
flag = calc_dist(false, 0);
//목적지에 도달하지 못하면 반복문 종료
if (!flag) {
taxi_fuel = -1;
break;
}
}
cout << taxi_fuel;
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 2580번] 스도쿠 / C++ (0) | 2020.10.09 |
---|---|
[백준 19236번] 청소년 상어 / C++ (0) | 2020.10.07 |
[백준 12865번] 평범한 배낭 / C++ (0) | 2020.10.05 |
[백준 14503번] 로봇 청소기 / C++ (0) | 2020.10.05 |
[백준 1753번] 최단경로 / C++ (0) | 2020.10.03 |