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

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

19238번: 스타트 택시

1. 주의할 점

- 변수들을 헷갈리지 않도록 한다

- 초기화를 잘 처리해준다

- 특정 조건에 맞는 우선순위 큐를 사용하여 다음으로 태울 손님을 구한다

 

2. 구현

- 길에 대한 정보를 Arr[][] 함수에 저장한다

- 손님의 시작위치, 도착지점 위치를 P[][4] 배열에 담는다

- Need_fuel[] 배열에 대한 초기화를 수행한다. 해당 배열은 손님의 탑승위치 -> 도착위치까지의 최단 거리를 미리 구하여 값을 저장하는 배열이다

- People[][] 배열에 손님이 위치해 있을 경우, 몇 번 손님이 위치해 있는지 표시한다

- Cal() 함수를 통해 미리 Need_fuel[] 배열에 값을 저장한다

- mvToPeople 함수를 손님의 수 만큼 수행하며, 최단 거리에 위치한 손님들을 우선순위 큐에 넣은 후, 가장 조건에 부합하는 사람번호에 대한 처리를 수행한다. 이후, 부합하는 손님이 있는 경우에는 손님의 번호를, 없는 경우에는 -1을 반환한다. 이 때, 택시의 위치 변경, 남은 연료 수정한다

 

#define MAX 987654321
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int x,y,val,idx;
};
struct cmp{
    bool operator()(info &a, info &b){
        if(a.val==b.val){
            if(a.y==b.y)
                return a.x> b.x;
            return a.y > b.y;
        }
        return a.val > b.val;
    }
};
info tmp;
int arr[21][21];
int people[21][21];     //해당 위치에 있는 사람 표시
int num,mv,fuel;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int tx,ty,result;
bool finish[401]={false,};
int p[401][4];       //sy,sx,ey,ex
int need_fuel[401];      //손님의 위치->도착지점까지 필요한 연료
bool check[21][21]={false,};

void cal(){     //손님의 위치->도착지점까지 필요한 연료 계산 함수
    for(int i=1;i<=mv;i++){
        for(int j=1;j<21;j++)
            for(int k=1;k<21;k++)
                check[j][k]=false;
        queue<info> q;
        tmp.x = p[i][1];
        tmp.y = p[i][0];
        tmp.val = 0;
        check[tmp.y][tmp.x] = true;
        q.push(tmp);
        while(!q.empty()){
            int cx = q.front().x;
            int cy = q.front().y;
            int cv = q.front().val;
            q.pop();
            if(cx==p[i][3] && cy == p[i][2]){
                need_fuel[i] = cv;
                break;
            }
            for(int j=0;j<4;j++){
                int nx = cx + dx[j];
                int ny = cy + dy[j];
                if(nx>0 && ny>0 && nx<=num && ny<=num && arr[ny][nx]==0 && !check[ny][nx]){
                    check[ny][nx]=true;
                    tmp.x = nx;
                    tmp.y = ny;
                    tmp.val = cv+1;
                    q.push(tmp);
                }
            }
        }
    }
}

int mvToPeople(){
    for(int j=1;j<21;j++)
        for(int k=1;k<21;k++)
            check[j][k]=false;
    queue<info> q;
    tmp.x = tx;
    tmp.y = ty;
    tmp.val = 0;
    q.push(tmp);
    check[ty][tx]=true;
    int mini=MAX;
    int arrived = -1;
    priority_queue<info,vector<info>,cmp> pq;

    while(!q.empty()){
        int cx = q.front().x;
        int cy = q.front().y;
        int cv = q.front().val;
        q.pop();
        if(people[cy][cx] && !finish[people[cy][cx]]){
            tmp.x = cx;
            tmp.y = cy;
            tmp.val = cv;
            tmp.idx = people[cy][cx];
            pq.push(tmp);
            mini = cv;
        }
        if(cv>=mini) continue;
        for(int i=0;i<4;i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(nx>0 && ny>0 && nx<=num && ny<=num && !check[ny][nx] && arr[ny][nx]==0 && cv<=fuel){
                check[ny][nx]=true;
                tmp.x = nx;
                tmp.y = ny;
                tmp.val = cv+1;
                q.push(tmp);
            }
        }
    }
    while(!pq.empty()){
        arrived = pq.top().idx;
        fuel-=pq.top().val;
        tx = p[arrived][3];
        ty = p[arrived][2];
        break;
    }
    return arrived;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> num>>mv>>fuel;
    for(int i=1;i<=num;i++)
        for(int j=1;j<=num;j++)
            cin >> arr[i][j];
    for(int i=1;i<=mv;i++)
        need_fuel[i]=MAX;
    cin >> ty>>tx;
    for(int i=1;i<=mv;i++){
        cin>>p[i][0]>>p[i][1]>>p[i][2]>>p[i][3];
        people[p[i][0]][p[i][1]]=i;
    }

    int cnt=0;      //데려다 준 사람 수
    cal();
    while(cnt<mv){
        int pidx = mvToPeople();
        if(pidx==-1){
            fuel = pidx;
            break;
        }
        if(fuel>=need_fuel[pidx]){
            fuel+=need_fuel[pidx];
            cnt++;
            finish[pidx]=true;
        }
        else{
            fuel = -1;
            break;
        }
    }
    cout << fuel;
    return 0;
}