백준 스타트택시

www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

 

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

 

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

 

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 987654321;
int map[21][21];
int people_cost[21][21];
int dist[21][21];
int dir[4][2]= { {1,0} , {0,1} , {-1,0}, {0,-1}};
int N , M , L;
struct People{
    int pY , pX , dY ,dX;
};
struct Taxi{
    int Y , X , L;
};
vector < People > peoples;
Taxi taxi;
bool gotaxi(int y , int x , int pcost){
    int distY ,distX , dIdx;
    for(int i = 0 ; i < N ;i ++){ //초기화
        for(int j = 0 ; j < N ;j++){
            dist[i][j] = INF;
        }
    }
    for(int i = 0 ; i < peoples.size() ;i++){
        if(peoples[i].pY == y && peoples[i].pX == x){
            distY = peoples[i].dY;
            distX = peoples[i].dX;
            dIdx = i;
            break;
        }
    }
    int time = 1;
    queue <pair <int , int > > q;
    q.push({ y , x});
    dist[y][x] = 0;
    if(y == distY && x == distX){
        int totalCost = taxi.L - pcost - 0 ;
        if ( totalCost < 0  ){
                return false;
        }else{
            map[y][x] = 0;
            taxi.Y = distY;
            taxi.X = distX;
            taxi.L  = (totalCost) + (0 * 2);
            peoples.erase(peoples.begin()+dIdx);
            return true;
        }
    };

    while (!q.empty()){
        int qsize = q.size();
        for(int i = 0 ; i < qsize ;i++){
            int curY = q.front().first;
            int curX = q.front().second;
            q.pop();
            for(int  k= 0 ; k < 4;k++){
                int nextY = curY + dir[k][0];
                int nextX = curX + dir[k][1];
                if(nextY < 0 || nextX < 0 || nextY >= N || nextX >= N || map[nextY][nextX] == 1) continue;
                if( (map[nextY][nextX] == 0 || map[nextY][nextX] == 2) && dist[nextY][nextX] > time){
                    dist[nextY][nextX] = time;
                    q.push({ nextY , nextX });
                    if(nextY == distY && nextX == distX){
                        int totalCost = taxi.L - pcost - time ;
                        if ( totalCost < 0  ){
                            return false;
                        }else{
                            map[y][x] = 0;
                            taxi.Y = distY;
                            taxi.X = distX;
                            taxi.L  = (totalCost) + (time * 2);
                            peoples.erase(peoples.begin()+dIdx);
                            return true;
                        }
                    };
                }
            }
        }
        time++;
    }
    return false;
}
bool find_people(int y , int x){
    for(int i = 0 ; i < N ;i ++){
        for(int j = 0 ; j < N ;j++){
            people_cost[i][j] = INF;
        }
    }
    queue <pair <int , int > > q;
    vector <pair < int , pair <int,int> > > p_list;
    q.push({ y , x});
    people_cost[y][x] = 0;
    if(map[y][x] == 2){
        p_list.push_back( { 0, {y , x } });
        if(p_list.size() == 0 || taxi.L - p_list[0].first < 0 ){
            return false;
        }
        else{
            return gotaxi(p_list[0].second.first , p_list[0].second.second , p_list[0].first);
        }
    } 

    int time = 1;
    while (!q.empty()){
        int qsize = q.size();
        for(int i = 0 ; i < qsize ;i++){
            int curY = q.front().first;
            int curX = q.front().second;
            q.pop();
            for(int  k= 0 ; k < 4;k++){
                int nextY = curY + dir[k][0];
                int nextX = curX + dir[k][1];
                if(nextY < 0 || nextX < 0 || nextY >= N || nextX >= N || map[nextY][nextX] == 1) continue;
                if( (map[nextY][nextX] == 0 || map[nextY][nextX] == 2) && people_cost[nextY][nextX] > time){
                    people_cost[nextY ][nextX] = time;
                    q.push({ nextY , nextX });
                    if(map[nextY][nextX] == 2) p_list.push_back( { time, {nextY , nextX } });
                }
            }
        }
        time++;
    }
    sort( p_list.begin() , p_list.end() );
    if(p_list.size() == 0 || taxi.L - p_list[0].first < 0 ){
        return false;
    }
    else{
        return gotaxi(p_list[0].second.first , p_list[0].second.second , p_list[0].first);
    }
}
void input_data(){
    cin >> N >> M >> taxi.L;
    for(int i = 0 ; i < N ;i ++){
        for(int j = 0 ; j < N ;j++){
            cin >> map[i][j];
        }
    }
    cin >> taxi.Y >> taxi.X;
    taxi.Y--;
    taxi.X--;
    for(int i = 0 ; i < M ;i++){
        People p;
        cin >> p.pY >> p.pX >> p.dY >>p.dX;
        p.pY--;
        p.pX--;
        p.dY--;
        p.dX--;
        peoples.push_back(p);
        map[p.pY][p.pX] = 2;
    }
}
void sol(){
    bool flag = true;
    while (true){
        if( peoples.size() == 0) break;
        if ( find_people(taxi.Y , taxi.X) == false ) {
            flag = false;
            break;
        }
    }
    if(flag){
        cout <<taxi.L;
    }else{
        cout << -1 ;
    }
}
int main(){
    input_data();
    sol();
    return 0;
}