[BOJ] 19238 : 스타트 택시

문제 링크

19238번: 스타트 택시 (acmicpc.net)

19238번: 스타트 택시

모든 손님을 최단거리로 태우고 싶어하는 백준이를 도와주자.

 

풀이

백준이가 운전하는 택시는 현재 위치에서 가장 가까운 손님을 태우고, 그 손님을 목적지로 데려다준다.

만약 연료가 부족해서 손님을 태우지 못하거나, 손님을 태우고 목적지까지 가지 못한다면 -1을 출력하고 종료한다.

연료가 충분해서 손님을 태워서 목적지에 데려다 줄 수 있다면, 손님의 위치에서 목적지까지 사용한 연료 x 2 만큼의 연료가 충전된다.

모든 손님을 다 태워다 줄 수 있다면, 다 태운 후 남은 연료의 양을 출력하고 그럴 수 없다면 -1을 출력한다.

 

  1. 가장 가까운 손님 찾기

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다.
그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 
그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.

가장 가까운 손님이 1명이라면 다행이지만 거리가 같은 손님이 여러명 있다면 위의 조건에 따라 손님의 우선순위를 정한다.

BFS를 이용해서 가장 가까운 거리에 있는 손님을 탐색한다. 그리고 그 손님들의 위치를 벡터에 저장한다. 탐색을 마친 후에 벡터에 값이 하나만 들어있다면 최단거리의 손님이 1명 뿐이라는 뜻이므로 그 손님을 태운다. 벡터에 값이 여러개 들어있다면 최단거리의 손님이 여러명이라는 뜻이므로 이 벡터를 정렬해 준 후 가장 앞에있는 손님을 태운다.

pair<int,int>의 벡터를 정렬하게 되면 값이 작은 순으로 정렬되기 때문에 맨 앞에 있는 손님이 행과 열의 번호가 가장 작은 손님이다.

 2. 손님 태워다드리기

손님마다 목적지가 다르기때문에 손님 번호별로 잘 구분해서 손님의 목적지를 받아두어야한다.

이번에는 목적지가 정해져있는 BFS를 통해서 손님을 목적지까지 데려다주는데 필요한 최소 연료를 찾는다.

현재 가지고 있는 연료보다 필요한 연료가 더 많으면 손님을 못데려다 주는 것이므로 -1을 출력하고 종료한다.

그렇지 않으면, 현재 연료 - 필요한 연료 + 필요한 연료 * 2 만큼의 연료가 남게 되므로

즉 현재 연료 + 필요한 연료 만큼 충전해주면 된다.

 

이렇게 M명의 손님을 태워다 드린 후 남은 연료를 출력해주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 20 + 5;
int N, M, Fuel;
int Map[MAX_N][MAX_N];
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int Client[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
vector<pair<pair<int,int>, int>> client;
vector<pair<int, int>> goal;
 
void BFS(pair<int, int> st);
bool is_ok(pair<int, int> next);
int Take_Client(pair<int, int> st, pair<int, int> ed);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> Fuel;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> Map[i][j];
 
    pair<int, int> Taxi; //택시 위치
    cin >> Taxi.first >> Taxi.second;
    goal.push_back({ 0, 0 });
 
    for (int i = 1; i <= M; i++) {
        pair<int, int> position;
        cin >> position.first >> position.second;
        pair<int, int> Goal;
        cin >> Goal.first >> Goal.second;
        Client[position.first][position.second] = i;
        goal.push_back(Goal);
    }
 
    
    for (int i = 1; i <= M; i++) {
        BFS(Taxi);
        if (client.empty()) {
            cout << "-1\n";
            return 0;
        }
        sort(client.begin(), client.end());
        int Next_Client = Client[client[0].first.first][client[0].first.second];
        Fuel -= client[0].second;
        Taxi = { client[0].first.first, client[0].first.second };
        pair<int, int> Goal = goal[Next_Client]; //현재 손님의 목적지
        int Require_Fuel = Take_Client(Taxi, Goal);
        if (Require_Fuel == -1) {
            cout << "-1\n";
            return 0;
        }
        if (Fuel >= Require_Fuel) {
            Taxi = Goal;
            Client[client[0].first.first][client[0].first.second] = 0;
            Fuel += Require_Fuel;
            continue;
        }
        else {
            cout << "-1\n";
            return 0;
        }
    }
    cout << Fuel << "\n";
    return 0;
}
 
void BFS(pair<int, int> st) {
    queue<pair<pair<int, int>, int>> q;
    q.push({ st,0 });
    int Min_distance = INF;
    memset(visited, false, sizeof(visited));
    client.clear();
    while (!q.empty()) {
        pair<int, int> now = q.front().first;
        int distance = q.front().second;
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        if (Min_distance < distance)
            continue;
        if (Client[now.first][now.second]) {
            if (Min_distance > distance) {
                Min_distance = distance;
                client.clear();
                client.push_back({now,distance});
            }
            else if (Min_distance == distance) {
                client.push_back({ now,distance });
            }
            continue;
        }
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            if (is_ok(next))
                q.push({ next, distance + 1});
        }
    }
}
 
int Take_Client(pair<int, int> st, pair<int, int> ed) {
    queue<pair<pair<int, int>, int>> q;
    q.push({ st, 0 });
    memset(visited, false, sizeof(visited));
    while (!q.empty()) {
        pair<int, int> now = q.front().first;
        int distance = q.front().second;
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        if (now == ed)
            return distance;
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            if (is_ok(next))
                q.push({ next, distance + 1 });
        }
    }
    return -1;
}
 
bool is_ok(pair<int, int> next) {
    if (next.first < 1 || next.first > N || next.second < 1 || next.second > N
        || visited[next.first][next.second] || Map[next.first][next.second])
        return false;
    return true;
}