[백준] 19238번 : 스타트 택시 - BFS C++

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

19238번: 스타트 택시

1.문제설명

택시가 손님을 정해진 위치에 데려다 주면서 이동한 거리를 바탕으로 연료의 양을 조건에 따라 계산해야하는 문제이다.

 

이 문제를 풀기 위해 BFS가 여러번 쓰인다.

 

 

1. 첫번째로 택시가 모든 손님과 모든 손님의 도착점으로 이동할 수 있는지 검사해야한다.

벽으로 경로가 끊어져 있을 수 있기 때문에 Flood Fill 방식으로 계산한다.

 

2. 두번째로 가까이 있는 손님을 구하기 위해 Flood Fill 방식으로 다시

현재 택시의 위치와 손님과의 거리를 구한다.

이때 주의해야할 점은 손님을 발견하자마자 BFS를 종료하면 안되고,

손님을 발견하더라도 전체 맵을 다 돌 때까지 BFS를 실행해야한다.

 

map의 크기가 작기 때문에 시간초과에 걸리지 않는다.

이렇게 해야하는 이유는 먼저 모든 손님에 대하여 각 손님까지의 거리를 구한 후

거리가 동일한 경우 행과 열의 숫자를 보고 손님을 정해야하기 때문이다.

만약 BFS를 돌다 손님 하나를 발견하자마자 종료한다면

같은 거리에 위치했지만 행과 열 정보에서 우선순위를 지니는 손님을 탐색하지 못한다.

 

 

3. 세번째는 손님 ---- 도착점 사이의 거리를 구하기 위해 BFS를 사용한다.

Map의 중간 중간 벽이 존재하기 때문에 BFS나 DFS로 거리를 구해야 한다.

 

이러한 세가지 기능을 구현해주면 문제를 해결할 수 있다.

 

---

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
int N, M, F; //F : 초기연료
bool arr[21][21]; //벽
int stx, sty; //driver 시작점
int guestInfo[403][4]; // guest마다 시작x,y 종점x,y
bool checkGuestEnd[403];

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

void Input();

bool gameCheck(int _stx, int _sty) { //flood Fill -> driver로부터 guest 시작점,종점 경로가 연결 되어 있는지확인
    bool ch[21][21] = {0};
    queue<pair<int, int> > Q;

    ch[_stx][_sty] = 1;
    Q.push({_stx, _sty});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

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

            if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
            if (ch[nx][ny] || arr[nx][ny]) continue;
            Q.push({nx, ny});
            ch[nx][ny] = 1;
        }
    }

    for (int i = 1; i <= M; i++) {
        int x = guestInfo[i][0];
        int y = guestInfo[i][1];
        int nx = guestInfo[i][2];
        int ny = guestInfo[i][3];

        if (ch[x][y] == 0 || ch[nx][ny] == 0) {
            return false;
        }
    }
    return true;
}

pair<int,int> chooseGuest(int _stx, int _sty){
    int ch[21][21] = {0};
    queue<pair<int, int> > Q;

    ch[_stx][_sty] = 1;
    Q.push({_stx, _sty});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

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

            if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
            if (ch[nx][ny] > 0 || arr[nx][ny]) continue;
            Q.push({nx, ny});
            ch[nx][ny] = ch[cur.first][cur.second] + 1;

        }
    }

    int minDist = 100000;
    int nextGuest = -1;

    for(int i=1; i<=M; i++){
        if(checkGuestEnd[i]) continue;

        int curDist = ch[guestInfo[i][0]][guestInfo[i][1]];
        if( curDist< minDist){
            nextGuest = i;
            minDist = curDist;
        }
        else if(curDist == minDist){
            if(guestInfo[nextGuest][0] > guestInfo[i][0]){
                nextGuest = i;
            }
            else if(guestInfo[nextGuest][0] == guestInfo[i][0]){
                if(guestInfo[nextGuest][1] > guestInfo[i][1]){
                    nextGuest = i;
                }
            }
        }
    }

    return {nextGuest, minDist-1};
}

int calDistance(int _stx, int _sty, int enx, int eny){
    int ch[21][21] = {0};
    queue<pair<int, int> > Q;

    ch[_stx][_sty] = 1;
    Q.push({_stx, _sty});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

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

            if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
            if (ch[nx][ny] > 0 || arr[nx][ny]) continue;
            Q.push({nx, ny});
            ch[nx][ny] = ch[cur.first][cur.second] + 1;
            if(nx==enx && ny==eny) break;
        }
    }

    return ch[enx][eny]- 1;
}

bool allGuestGoHome(){
    for(int i=1; i<=M; i++){
        if(!checkGuestEnd[i]) return false;
    }
    return true;
}


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


    //벽 때문에 깃발이나 손님한테 갈 수 없는 경우
    if (!gameCheck(stx,sty)) {
        cout << -1 << '\n';
        return 0;
    }


    while(!allGuestGoHome()) {
        auto nextGuest = chooseGuest(stx, sty);
        int guest = nextGuest.first;
        int toGuestDist = nextGuest.second;
        int toFlagDist = calDistance(guestInfo[guest][0], guestInfo[guest][1], guestInfo[guest][2], guestInfo[guest][3]);


        if(F<toGuestDist + toFlagDist){
            cout << -1 << '\n';
            return 0;
        }
        else{
            //guest 집에감, 연료 동기화
            checkGuestEnd[guest] = 1;
            F = F - toGuestDist + toFlagDist;

            //driver 이동
            stx = guestInfo[guest][2];
            sty = guestInfo[guest][3];
        }
    }

    cout << F << '\n';
}


void Input() {
    cin >> N >> M >> F;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
    //driver start
    cin >> stx >> sty;

    for (int i = 1; i <= M; i++) {
        cin >> guestInfo[i][0] >> guestInfo[i][1] >> guestInfo[i][2] >> guestInfo[i][3]; //start x,y / end x, y
    }


}