백준 g2 19238 스타트 택시 c++

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

19238번: 스타트 택시

 

문제 설명

N*N 보드에 각각 현재 택시의 위치, M명의 승객들의 출발점과 도착점이 주어진다.

택시는 가장 가까운 손님부터 태우고, 그 손님의 도착점에 내려준다. 그 이후로 다시 가장 가까운 손님부터 태우기를 반복한다.

택시는 1칸 갈 때마다 연료를 소모한다.

승객을 도착점에 내려주면, 택시는 승객을 태우고 소모한 연료의 2배를 다시 획득한다.

 

택시가 달리다가 연료가 다 닳으면 모든 승객을 옮길 수 없으므로 -1을 출력한다.

모든 승객을 태우고 난 후, 남은 연료를 출력한다.

 

풀이

그냥 구현문제이므로 하나하나씩 구현하면 된다.

1. 최단 거리 구하기 (bfs)
	if 태울 수 있는 승객이 없으면
    	그 승객은 절대 태울 수 없으므로 오늘 영업 끝
	if 최단거리 > 남은 연료
    	return 오늘 영업 끝
    else
    	연료 -= 거리
        택시 위치 업데이트
        승객 삭제
2. 태운 승객의 도착점까지의 거리 (bfs)
	if 구한 최단거리 > 남은 연료
    	return 오늘 영업 끝
    else 
    	남은 연료 += 최단 거리
        택시 위치 업데이트

 

1. 모든 승객까지의 최단 거리 구하기

 - bfs로 모든 좌표의 거리를 구한다음, 승객의 좌표를 이용해서 최단 거리를 구해줬다.

나는 if 문으로 구현했지만 이를 priority queue를 사용해 <거리, i좌표, j좌표>가 최소가 되도록 구현할 수도 있다. (기본적으로 priority queue는 내림차순이라는 걸 기억하자)

 

실수한 점

int cusDist = vis[customer[i].first][customer[i].second];
if (cusDist == 0) continue; // 갈 수 없는 경우면 패스

택시 ~ 모든 승객 간의 최소 거리를 구할 때, 승객에게 갈 수 없으면 (vis가 0이면!!) continue했어야했는데 하지 않아서 86%에서 계속 틀렸습니다 가 나왔다. 좀 중요한 실수 같은데 86%까지 다 맞았다는 게 신기했다 .. 작은 실수인 줄 알았는데 작은 실수가 아니었던 거임

 

참고한 반례: https://www.acmicpc.net/board/view/54373

 

전체 코드

/*boj g2 19238 스타트 택시*/
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#define MAXN 22
using namespace std;

int N, M, fuel;
pair<int, int> tCur;
vector<pair<int, int>> customer;
vector<pair<int, int>> destination;
int board[MAXN][MAXN];
int vis[MAXN][MAXN];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void print() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << vis[i][j] << "\t";
        }
        cout << "\n";
    }
    cout << "\n===================\n";
}
void input() {
    cin >> N >> M >> fuel;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    int x, y;
    cin >> x >> y;
    tCur = {x - 1, y - 1};

    for (int i = 0; i < M; i++) {
        int sx, sy, dx, dy;
        cin >> sx >> sy >> dx >> dy;
        customer.push_back({sx - 1, sy - 1});
        destination.push_back({dx - 1, dy - 1});
    }
}

void bfs() { // cur에서 시작해서 전체 맵을 모두 순회
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            vis[i][j] = 0;
    queue<pair<int, int>> Q;

    vis[tCur.first][tCur.second] = 1;
    Q.push({tCur.first, tCur.second});

    while (!Q.empty()) {
        pair<int, int> cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (vis[nx][ny] > 0) continue;
            if (board[nx][ny] == 1) continue;

            vis[nx][ny] = vis[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }
}

pair<int, int> getMinDist() { // <최단거리, 승객 번호>를 return
    // 1. 일단 전체 board의 bfs 구하기
    bfs();
    // 2. 택시-승객까지의 최단 거리 구하기
    int mn = 999999;
    int mn_x = -1;
    int mn_y = -1;
    int cusNum = -1;
    for (int i = 0; i < M; i++) {
        if (customer[i].first == -1) // 이미 완료된 승객이면 continue
            continue;

        int cusDist = vis[customer[i].first][customer[i].second];
        if (cusDist == 0) continue; // 갈 수 없는 경우면 패스

        if (mn > cusDist) {
            mn = cusDist;
            mn_x = customer[i].first;
            mn_y = customer[i].second;
            cusNum = i;
        } else if (mn == cusDist) {
            if (mn_x > customer[i].first) {
                mn = cusDist;
                mn_x = customer[i].first;
                mn_y = customer[i].second;
                cusNum = i;

            } else if (mn_x == customer[i].first) {
                if (mn_y > customer[i].second) {
                    mn = cusDist;
                    mn_x = customer[i].first;
                    mn_y = customer[i].second;
                    cusNum = i;
                }
            }
        }
    }
    return make_pair(mn - 1, cusNum); // 갈 수 있는 곳이 없으면 999999, -1 반환
}

int getDestDist(int x, int y) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            vis[i][j] = 0;
    queue<pair<int, int>> Q;

    vis[tCur.first][tCur.second] = 1;
    Q.push(tCur);

    while (!Q.empty()) {
        pair<int, int> cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (vis[nx][ny] > 0) continue;
            if (board[nx][ny] == 1) continue;

            vis[nx][ny] = vis[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }

    // 승객의 도착지에 도착할 수 없으면
    return vis[x][y] - 1;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    int t = M;
    while (t--) {
        // 1. 최단 거리 승객 구하기
        int mnDist, cusNum;
        tie(mnDist, cusNum) = getMinDist();
        if (cusNum == -1) { // 갈 수 있는 곳이 없으면
            cout << -1 << "\n";
            return 0;
        }
        if (mnDist > fuel) { // 연료가 다 닳으면
            cout << -1 << "\n";
            return 0;
        } else {
            fuel -= mnDist;
            tCur.first = customer[cusNum].first;
            tCur.second = customer[cusNum].second;
            customer[cusNum] = {-1, -1};
        }
        // cout << tCur.first << " " << tCur.second << "\n";

        // 2. 승객 태웠고, 승객의 목적지 까지 이동
        int destDist = getDestDist(destination[cusNum].first, destination[cusNum].second);
        if (destDist == -1) {
            cout << -1 << "\n";
            return 0;
        }

        if (destDist > fuel) {
            cout << -1 << "\n";
            return 0;
        } else {
            fuel += destDist;
            tCur.first = destination[cusNum].first;
            tCur.second = destination[cusNum].second;
        }
        // cout << tCur.first << " " << tCur.second << "\n";
        // print();
    }

    cout << fuel << "\n";
}