[백준] 19238: 스타트 택시(C++)

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

소요 시간

골드 2 기준 40분 정도가 소요되었습니다. 구현할 것이 최소거리 구하는 로직 밖에 없기 때문에 괜찮았습니다.

갑자기 존댓말을 사용하네요. 요즘 글에 공감이 몇 개 찍히는 것 보니 글을 찾아보시는 분들이 꽤 있는 것 같아서 예의를 차리는 것입니다.

 

구상

문제를 풀기 위해 필요한 것은 두 점 사이의 최소거리를 구하는 함수입니다. 이것을 가지고 각 고객과의 거리를 구하고, 고객을 태우고 고객의 목적지까지 가는 거리를 구할 수 있습니다. 그 후로부터는 운행종료 조건과 연료 충전 조건을 문제에서 시키는 대로 구현하면 됩니다.

 

거리를 구하는 함수는 bfs로 구현했습니다. 벽이 있거나 이미 방문한 경우는 제외하면서 bfs로 방문하여, 방문한 좌표와 걸린 시간을 큐에 저장했습니다. 도착점에 도착했으면 거기 도달하는데 걸리는 시간이 최단시간이므로 해당 시간을 리턴합니다.

 

주의할 점은 '승객을 태우러 갈 수 없거나 승객을 태우고 도착지에 도착하지 못하는 경우' -1을 리턴해야 한다는 것입니다. 저는 이렇게 도달하지 못하는 지점은 최단시간으로 INT_MAX를 계산하게끔 했습니다. 연료에서 INT_MAX를 빼니까 무조건 연료가 다 바닥났다는 판단 로직에 걸릴 것 같습니다. 그런데 (승객을 태우러 가는 시간 + 승객을 태우고 도착지에 가는 시간)을 남은 연료에서 뺀다면, 이 덧셈 과정에서 오버플로가 일어나서 두 시간 중 하나가 INT_MAX값이어도 남은 연료가 0보다 작아지지 않을 수도 있습니다. 따라서 연료가 음수인 경우뿐만 아니라 시간이 무한대인 경우까지 확인하여 -1을 리턴해 주도록 했습니다.

 

저는 코드의 간결성을 위해 x,y를 일차원 정수로 표현했습니다.(x*열개수+y) 모든 고객들의 출발점, 도착점, 백준의 위치 등 2차원 좌표를 관리할 일이 많은데, 이것이 약간 귀찮게 느껴졌기 때문입니다. 자신이 헷갈리지만 않으면 좋은 방법인 듯 합니다. 저는 오히려 2차원 좌표를 x,y로 관리하는게 더 헷갈리네요...

 

코드

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<queue>
#include<cmath>
#include<algorithm>

using namespace std;
vector<pair<int, int> > customers;
vector<vector<int> > board;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int get_minDist(int sxy, int dxy, int n) {
    //sxy에서 dxy로 가는 최단경로를 구함
    bool visited[n+1][n+1];
    for(int i=0; i<=n; i++) fill_n(visited[i], n+1, false);

    queue<pair<int, int> > q;
    q.push(pair<int, int>(sxy, 0));

    while(!q.empty()) {
        if(q.front().first == dxy) {
            return q.front().second;
        }
        int x = q.front().first/(n+1); int y = q.front().first%(n+1);
        int dist = q.front().second;
        q.pop();

        for(int i=0; i<4; i++) {
            int nx = x+dx[i]; int ny = y+dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > n || board[nx][ny] == 1 || visited[nx][ny]) continue;
            visited[nx][ny] = true;
            q.push(pair<int, int>(nx*(n+1) + ny, dist+1));
        }
    }

    return INT_MAX; //dxy에 도착할 수 없는 경우
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m, fuel;
    cin >> n >> m >> fuel;
    
    board.resize(n+1);
    for(int i=1; i<=n; i++) {
        board[i].resize(n+1);
        for(int j=1; j<=n; j++) {
            cin >> board[i][j];
        }
    }

    int bxy; int bx; int by;
    cin >> bx >> by;
    bxy = bx*(n+1) + by;
    
    customers.resize(m);
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        customers[i].first = x*(n+1) + y; //출발지
        cin >> x >> y;
        customers[i].second = x*(n+1) + y; //도착지
    }
    sort(customers.begin(), customers.end());

    while(!customers.empty()) {
        int min_customer = 0; int b_to_c = INT_MAX;
        for(int i=0; i<customers.size(); i++) {
            int dist = get_minDist(bxy, customers[i].first, n);
            if(dist < b_to_c) {
                min_customer = i;
                b_to_c = dist;
            }
        }
        int c_to_d = get_minDist(customers[min_customer].first, customers[min_customer].second, n);
        fuel -= (b_to_c + c_to_d);
        if(fuel < 0 || b_to_c == INT_MAX || c_to_d == INT_MAX) {
            cout << "-1" << endl;
            return 0;
        }
        fuel += 2*c_to_d;
        bxy = customers[min_customer].second;
        customers.erase(customers.begin() + min_customer);
    }
    cout << fuel << endl;

    return 0;
}