[백준 19238번] 스타트 택시

문제 링크: https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

<문제 풀이> 시뮬레이션, 우선순위 큐, BFS, 최단거리

먼저 택시를 기준으로 BFS를 사용해서 최단거리를 갱신합니다. 이때 다음 좌표로 이동할 때 택시의 연료가 부족하면 이동하면 안 됩니다. 현재 연료로 다음 좌표로 이동할 수 있으면 해당 손님의 좌표를 다음과 같은 기준으로 우선순위 큐에 기록합니다.

1. 현재 위치에서 최단거리가 가장 짧은 승객을 고른다.

2. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을 고른다.

3. 그런 승객도 여러  명이면 그중 열 번호가 가장 작은 승객을 고른다.

아래 코드와 같이 우선순위 큐를 선언하면 우선순위 큐의 top에는 위 조건을 만족하는 손님이 존재하게 됩니다.

 

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;

 

BFS가 끝나면 우선순위 큐의 top에 존재하는 손님까지의 거리를 리턴하면 되고 만약 우선순위 큐가 비어있다면 연료가 부족해서 손님을 태우지 못한 경우이니 -1을 리턴하면 됩니다.

 

택시 BFS가 끝나면 이제 손님 BFS를 사용하면 됩니다.

 

손님 BFS에서 출발점과 도착점을 알고 있어야 하는데 단순히 2차원 배열에 손님의 도착 정보를 특정 값 형태로 저장하게 되면 안 됩니다.

 

왜냐하면 문제 조건에서 "모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다."라는 부분을 잘 이해하면 어떤 손님의 목적지가 어떤 손님의 출발지일 수도 있다는 걸 알 수 있습니다. 그래서 겹치는 부분을 처리하기 위해 해시맵을 이용해서 각 손님의 id와 목적지 좌표를 <key, value> 형태로 저장해야 합니다.

 

그리고 위 조건 때문에 택시가 목적지에 도착하자마자 바로 승객을 태울 수도 있기 때문에 이 부분도 예외처리를 해야 합니다.

 

<C++ 소스코드>

#include<iostream>
#include<queue>
#include<tuple>
#include<functional>
#include<utility>
#include<algorithm>
#include<unordered_map>
using namespace std;
 
#define X first
#define Y second
 
int n, m, fuel;
int board[21][21];
int visited[21][21];
int tx, ty; //택시 위치
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
unordered_map<int, pair<int, int> > um; //각 손님의 도착 위치
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;
 
int taxiBFS() {
    fill(&visited[0][0], &visited[20][21], -1);
    queue<pair<int, int> > Q;
    Q.push({ tx, ty });
    visited[tx][ty] = 0;
    if (board[tx][ty] > 0)pq.push({ visited[tx][ty], tx, ty }); //손님을 바로 태우는 경우
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 1 || ny < 1 || nx > n || ny > n)continue;
            if (visited[nx][ny] != -1 || board[nx][ny] == 1)continue; //이미 방문했거나 벽이면 무시
            if (visited[nx][ny] > fuel) continue; //다음 위치로 이동하는데 연료가 부족하면 무시
            visited[nx][ny] = visited[cur.X][cur.Y] + 1;
            if (board[nx][ny] > 0)pq.push({ visited[nx][ny], nx, ny }); // 다음 위치에 손님이 있는 경우
            Q.push({ nx, ny });
        }
    }
    if (pq.empty()) return -1; // 연료가 부족해서 손님을 못 태우는 경우
    else return get<0>(pq.top()); // 손님까지 거리를 리턴
}
 
int personBFS() {
    auto cur = pq.top(); pq.pop();
    pq = {};
    int d, x, y;
    tie(d, x, y) = cur;
    fill(&visited[0][0], &visited[20][21], -1);
    queue<pair<int, int> > Q;
    Q.push({ x, y });
    visited[x][y] = 0;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 1 || ny <1 || nx > n || ny > n)continue;
            if (visited[nx][ny] != -1 || board[nx][ny] == 1)continue;
            visited[nx][ny] = visited[cur.X][cur.Y] + 1;
            Q.push({ nx, ny });
            if (nx == um[board[x][y]].X && ny == um[board[x][y]].Y) {//목적지에 도착
                tx = nx;
                ty = ny;//택시 위치 목적지로 갱신
                board[x][y] = 0; //해당 승객 처리
                if (visited[nx][ny] > fuel) return -1; //만약 연료가 부족하면 실패
                return visited[nx][ny]; //return 소비한 연료
            }
        }
    }
    if (board[x][y]) return -1; // 목적지에 도착하지 못하면 승객을 처리하지 못함 -> return -1
}
 
void solution() {
    int cnt = 0;
    while (cnt < m) { //승객을 모두 처리할 때까지
        int consumeTaxi = taxiBFS();
        if (consumeTaxi == -1) {
            fuel = -1;
            return;
        }
        fuel -= consumeTaxi; //승객이 있는 곳까지 연료 감소
        int consumePerson = personBFS();
        if (consumePerson == -1) {
            fuel = -1;
            return;
        }
        fuel += consumePerson; // 목적지까지 연료 감소 후 소모한 연료 양 두 배 충전
        cnt++;
    }
    
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
     
    cin >> n >> m >> fuel;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> board[i][j];
        }
    }
    cin >> tx >> ty;
    for (int i = 0; i < m; i++) {
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        board[sx][sy] = i + 2; // 각 손님의 시작 위치 => 손님은 2이상의 key값으로 구분
        um[i + 2] = { ex, ey }; // 각 손님 식별 key는 2이상의 수
    }
    solution();
    cout << fuel;
    return 0;
}