[백준][19238] 스마트 택시

이 포스트는 백준 사이트의 스마트 택시 문제 풀이입니다.

문제

해결 과정

이 문제는 손님에게 방문하고 목적지까지 최단경로로 이동하는 것을 M번 반복하는 문제입니다.
이때, 현재 연료가 0이면 ‘-1’을 출력해야 하므로 중요한 것은 이동거리에 따른 연료의 소비입니다.

이 문제에서 사용할 최단 거리 알고리즘 후보와 가능 여부는 다음과 같습니다.

• 다익스트라: 그래프 간선에 가중치가 없어서 불가능.
• 플로이드-워셜: 그래프 간선에 가중치가 없어서 불가능.
• DFS: 연결된 노드가 너무 많아서 불가능.
• BFS: 넓은 범위를 탐색하므로 가능.

따라서 이 문제에서는 BFS를 활용하여 거리를 탐색하였습니다.

마지막으로 문제에서 연료를 소비할 때는 택시가 손님에게 갈 때와
손님이 택시를 타고 목적지로 갈 때 2가지가 있고
택시의 남은 연료가 0이 되기 전 목적지에 도착하면
\(손님을 태우고 이동한 거리 \times 2\) 만큼 연료를 충전할 수 있습니다.

위 과정을 순서대로 구현하면

1. 현재 택시 위치에서 가장 가까운 손님(위치에 따른 우선 순위 주위) 선택 및 최단 거리 이동
2. 손님의 출발지부터 목적지까지 최단거리로 이동

위 2가지 과정을 M번 반복하면 됩니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct POINT {
    int row, col;
};

int N, M, fuel;
int used_fuel = 0;
vector<vector<int>> board;
vector<vector<bool>> visited;
POINT taxi;
vector<vector<POINT>> clients;

int dir_row[4]{-1, 1, 0, 0};
int dir_col[4]{0, 0, -1, 1};

void input();
vector<POINT> find_closer_client();
bool check_remain_fuel(POINT start, POINT goal);

int main() {
    input();

    while(M--) {
        used_fuel = 0;

        auto client = find_closer_client();
        if(client.empty()) {
            cout << "-1";
            return 0;
        }

        if(check_remain_fuel(taxi,  client[0])) {
            fuel -= used_fuel;
            used_fuel = 0;
            
            if(check_remain_fuel(client[0], client[1])) {
                fuel += used_fuel;
            } else {
                cout << "-1";
                return 0;
            }
        } else {
            cout << "-1";
            return 0;
        }
    }

    cout << fuel;
    return 0;
}

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> fuel;
    board.assign(N + 1, vector<int>(N + 1, 0));
    for(int row = 1; row <= N; ++row) {
        for(int col = 1; col <= N; ++col) {
            cin >> board[row][col];
        }
    }
    
    cin >> taxi.row >> taxi.col;

    clients.assign(M, vector<POINT>(2, {0, 0}));
    for(int num = 0; num < M; ++num) {
        cin >> clients[num][0].row >> clients[num][0].col
            >> clients[num][1].row >> clients[num][1].col;
    }
}

vector<POINT> find_closer_client() {
    queue<pair<POINT, int>> q;
    q.push({taxi, fuel});

    visited.assign(N + 1, vector<bool>(N + 1, false));
    visited[taxi.row][taxi.col] = true;

    vector<vector<vector<POINT>>::iterator> goals;
    int curr_max_fuel = 0;
    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        for(auto it = clients.begin(); it != clients.end(); ++it) {
            if(curr.first.row == (*it)[0].row 
            && curr.first.col == (*it)[0].col
            && curr_max_fuel <= curr.second) {
                curr_max_fuel = curr.second;
                goals.emplace_back(it);
            }
        }

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.first.row + dir_row[dir];
            int new_col = curr.first.col + dir_col[dir];

            if(new_row < 1 || new_row > N || new_col < 1 || new_col > N)
                continue;
            if(1 == board[new_row][new_col])
                continue;
            if(visited[new_row][new_col])
                continue;
            visited[new_row][new_col] = true;
            
            q.push({POINT{new_row, new_col}, curr.second - 1});
        }
    }

    if(goals.empty()) {
        return vector<POINT>();
    } else {
        int small_row = 2e9, small_col = 2e9;
        POINT target_goal;
        vector<vector<POINT>>::iterator target;
        for(auto goal : goals) {
            if(((*goal)[0].row < small_row)
            ||
             ((*goal)[0].row == small_row && (*goal)[0].col < small_col)) {
                small_row = (*goal)[0].row;
                small_col = (*goal)[0].col;
                target_goal = (*goal)[1];
                target = goal;
            }
        }
        clients.erase(target);
        return {POINT{small_row, small_col}, target_goal};
    }

}

bool check_remain_fuel(POINT start, POINT goal) {
    queue<pair<POINT, int>> q;
    q.push(POINT{start, fuel});

    visited.assign(N + 1, vector<bool>(N + 1, false));
    visited[start.row][start.col] = true;

    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        if(curr.first.row == goal.row && curr.first.col == goal.col) {
            if(curr.second < 0) {
                break;
            } else {
                taxi = goal;
                if(used_fuel == 0) {
                    used_fuel = (fuel - curr.second);
                }
                return true;
            }
        }

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.first.row + dir_row[dir];
            int new_col = curr.first.col + dir_col[dir];

            if(new_row < 1 || new_row > N || new_col < 1 || new_col > N)
                continue;
            if(1 == board[new_row][new_col])
                continue;
            if(visited[new_row][new_col])
                continue;
            visited[new_row][new_col] = true;
            
            q.push({POINT{new_row, new_col}, curr.second - 1});
        }
    }

    fuel = -1;
    return false;
}

실행 결과