[ BOJ - 19238번 ] 스타트 택시 (C++)

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

 

 우선순위 큐를 이용해, 택시가 이동한 거리 -> 행 번호 -> 열 번호가 작은 순서로 BFS를 실행하는 방법으로 택시의 이동을 구현해 문제를 해결할 수 있을 것이라 생각했다.

 

[ 풀이 방법 ]

1. 택시 위치에서 승객 위치로 이동하는 기능

  - 택시에서 가장 가까운 승객에게 이동한다(거리가 같다면 행번호가 작은 승객, 행번호가 같다면 열번호가 작은 승객에게 이동).

  - 연료는 이동할 때 1씩 소모되며 연료가 남지 않았다면 이동을 종료한다.

 

2. 승객 위치에서 목적지 위치로 이동하는 기능

  - 승객에서 목적지까지 소모된 연료의 2배를 충전한다.

  - 연료는 이동할 때 1씩 소모되며 연료가 남지 않았다면 이동을 종료한다.

  - 목적지 도착과 동시에 연료 바닥난 경우에는 실패로 처리되지 않는다.

 

3. 목적지에 도달 후, 목적지 위치를 택시의 위치로 하여 1, 2번을 반복하는 기능

  - 택시가 이동할 때에는 항상 최단 거리로 이동하여야 한다.
  - 남아있는 승객이 없을 경우 택시에 남아있는 연료를 출력하고 반복을 종료한다.

  - 남아있는 승객에게 도달하지 못하거나 승객을 태우고 목적지에 도달하지 못할 경우(연료 부족, 벽에 둘러쌓여 이동 불가), -1을 출력하고 반복을 종료한다.

 

구현 계획

Taxi 구조체를 이용해 택시의 현재 위치(x, y)와 남은 연료, 이동 거리를 저장한다.

2차원 배열 board, passenger, dest에 벽이 있는 위치, 승객이 있는 위치, 목적지가 있는 위치를 저장한다.

승객과 목적지는 입력된 순서대로 1~M을 저장하여 각 배열에 표시한다.

 

1. 우선순위 큐를 이용해, 택시가 이동한 거리 -> 행 번호 -> 열 번호가 작은 순서로 BFS를 실행한다.

  - 승객에게 도착하기 전에 연료가 0이 된다면 반복을 종료하고 -1을 출력한다.

 

2.  승객이 탐색된 경우 승객을 태웠음을 표시하고 택시의 위치를 갱신한다.

  - 승객을 탐색하지 못하고 BFS가 종료될 경우,

  1. 남아있는 승객이 없다면 반복을 종료하고 택시에 남아있는 연료를 출력한다.

  2. 남아있는 승객이 있다면 반복을 종료하고 -1을 출력한다.

 

3. 탐색된 승객의 번호와 일치하는 목적지를 BFS 이용해 탐색하여 목적지에 도달할 경우 소모된 연료x2를 남은 연료에 더해주고 택시의 위치를 갱신한다.

  - 목적지 도달하기 전에 연료가 0이 된다면 반복을 종료하고 -1을 출력한다.

 

4. 모든 승객을 처리할 때까지 위 과정을 반복한다.

 

위 방법으로 기능들을 구현하였으나 정답을 맞추지 못했고, 디버깅에 실패하여 예외 테스트케이스를 확인한 뒤에야 해결할 수 있었다.

 

[ 회고 ]

 1. "모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다."라는 조건을 대충 읽고 넘겨, 뜻을 확실하게이해하지 못해 오류가 발생했다.

 -> 목적지의 위치는 승객끼리 겹칠 수 있으므로 3차원 배열을 이용해 승객별로 목적지를 저장해주어 해결하였다.

 

2. 1번 문제로 발새한 오류를 고치기 위해, 출력 결과를 통해 계획없이 코드를 수정하다가 추가로 오류들이 발생했다.

 

3. 승객의 이동 기능에는 처리했던, 목적지에 도달하지 못하고 BFS가 종료되는 경우를 처리하지 않아 오류가 발생했다.

 

4. 남아있는 연료가 0과 같거나 작을 경우 BFS를 종료하도록 구현할 경우, BFS 탐색 순서에 따라 오류가 발생할 수 있다.

-> 남아있는 연료가 0보다 작을 경우 BFS를 종료하도록 구현하고 문제를 해결하였다.

if(fuel < 0) {
    fail = true;
    vector<vector<bool>>().swap(visited);
    return;
}
if(dest[d][x][y] == d) {
    taxi = {x, y, fuel + 2*dist, 0};
    vector<vector<bool>>().swap(visited);
    res = fuel + 2*dist;
    return;
}

 

위 문제들을 모두 해결하여 정답을 맞출 수 있었다.

 

 글을 쓰며 다시보니 문제에 대한 이해와 구현 계획을 소홀히 하여 문제를 풀 올바르고 세부적인 방법을 생각하지 못했음을 깨달았다. 

앞으로는 문제를 읽는 데 시간을 더 투자하여 조건이 너무 많아 대충 읽고 넘어가 문제를 정확히 이해하지 못하는 일이 없도록 해야할 것이다.

 또한 구현 계획단계에서 생각했던 종료 조건이 문제에 직관적이지 않아 예상치 못한 오류들이 발생했기 때문에, 문제에서 주어진 조건을 처리할 때(조건문, flag 변수), 좀 더 문제에 어울리고 직관적인 값을 설정해야 할 것이다.

 

 가장 중요한 것은 최근 문제를 해결하지 못할 때마다 다짐하듯이, 구현 계획을 생각할 때 더 많은 시간을 투자하여 생각해둔 모든 접근 방법을 오류없이 정확하게 구현할 수 있는 방법을 계획해야 한다는 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

using namespace std;

struct Taxi {
    int x; int y;
    int fuel;
    int dist;
};

struct cmp {
    bool operator()(Taxi t1, Taxi t2) {
        
        if(t1.dist == t2.dist && t1.x == t2.x) return t1.y > t2.y;
        else if(t1.dist == t2.dist) return t1.x > t2.x;
        return t1.dist > t2.dist;
    }
};

int N, M, Fuel;
vector<vector<int>> board;
vector<vector<int>> passenger;
vector<vector<vector<int>>> dest;

int dirX[4] = {-1, 0, 0, 1};
int dirY[4] = {0, -1, 1, 0};

int res;
int remain;
bool ride = false;
bool fail = false;

void bfsTP(Taxi& taxi) {
    
    vector<vector<bool>> visited(N, vector<bool>(N));
    priority_queue<Taxi, deque<Taxi>, cmp> pq;
    pq.push(taxi);
    ride = false;
    
    while(!pq.empty()) {
        int x = pq.top().x;
        int y = pq.top().y;
        int fuel = pq.top().fuel;
        int dist = pq.top().dist;
        pq.pop();
        
        if(passenger[x][y]) {
            taxi = {x, y, fuel, 0};
            vector<vector<bool>>().swap(visited);
            ride = true;
            remain--;
            return;
        }
        
        for(int dir = 0; dir < 4; dir++) {
            
            int nx = x + dirX[dir];
            int ny = y + dirY[dir];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            
            if(!visited[nx][ny] && !board[nx][ny]) {
                visited[nx][ny] = true;
                pq.push({nx, ny, fuel-1, dist+1});
            }
        }
    }
    
    vector<vector<bool>>().swap(visited);
}

void bfsPD(Taxi& taxi) {
    
    vector<vector<bool>> visited(N, vector<bool>(N));

    priority_queue<Taxi, deque<Taxi>, cmp> q;
    q.push(taxi);
    int d = passenger[taxi.x][taxi.y];
    passenger[taxi.x][taxi.y] = 0;
    
    while(!q.empty()) {
        int x = q.top().x;
        int y = q.top().y;
        int fuel = q.top().fuel;
        int dist = q.top().dist;
        
        q.pop();
        
        if(fuel < 0) {
            fail = true;
            vector<vector<bool>>().swap(visited);
            return;
        }
        if(dest[d][x][y] == d) {
            taxi = {x, y, fuel + 2*dist, 0};
            vector<vector<bool>>().swap(visited);
            res = fuel + 2*dist;
            return;
        }

        
        for(int dir = 0; dir < 4; dir++) {
            
            int nx = x + dirX[dir];
            int ny = y + dirY[dir];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            
            if(!visited[nx][ny] && !board[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny, fuel-1, dist+1});
            }
        }
        
    }
    fail = true;
    vector<vector<bool>>().swap(visited);
}

void solve(Taxi& taxi) {
    
    while(true) {
        
        bfsTP(taxi);
        if(fail) {
            res = -1;
            return;
        }
        if(!ride) {
            if(remain > 0) {
                res = -1;
            }
            return;
        }
        
        bfsPD(taxi);
        if(fail) {
            res = -1;
            return;
        }
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> Fuel;

    board.resize(N, vector<int>(N));
    passenger.resize(N, vector<int>(N));
    dest.resize(M+1, vector<vector<int>>(N, vector<int>(N)));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    
    int x, y;
    cin >> x >> y;
    
    Taxi taxi = {x-1, y-1, Fuel, 0};
    
    for (int i = 1; i <= M; i++) {
        cin >> x >> y;
        passenger[x-1][y-1] = i;
        cin >> x >> y;
        dest[i][x-1][y-1] = i;
    }
    
    remain = M;
    
    solve(taxi);

    cout << res << '\n';
    
    return 0;
}