[백준19238번/삼성 코테 기출] - 스타트택시 c++

>> 문제읽고오기 <<

19238번: 스타트 택시

 

|| 문제 정리

우리는 일단 나의 위치, 승객의 위치, 승객의 목적지의 위치를 알면 된다.

그리고 미로에서 최단경로를 찾는 BFS를 구현해두면 쉬워보인다.

 

1. 나의 위치에서 가장 가까운 다음 승객을 고름

2. 고른 다음 승객까지의 거리 구함 (d)

        2-1)현재 연료로 다음 승객까지 갈 수 없으면 return -1

3. 현재 연료 - d 해주고 현재위치를 승객위치로 바꿔줌

4. 현재위치에서 목적지까지 거리 구함(dd)

       4-1) 현재 연료로 목적지까지 갈 수 없으면 return -1

5. 갈 수 있으면 현재연료 + dd (현재연료-dd+2dd)

6. 현재위치를 목적지 위치로 바꾸고 승객배열에 이미 탑승한 승객이라고 표시

 

주의해야 할 점은

아예 벽으로 막혀있어 갈 수 없는 맵이 주어졌을 경우도 생각해야한다는 것이다.....

#include <iostream>
#include<cstring>
#include <queue>
#define Nmax 20
#define Mmax 400
#define min(a, b) (((a)<(b)) ? (a) : (b))
using namespace std;


int Map[Nmax][Nmax] ={0,};
int visit[Nmax][Nmax];
int client[Mmax][5] ={0,};  // [0]태운승객인지아닌지,[1][2]승객위치,[3][4]승객목적지
int dr[] = { -1,0,1,0 };    //위 오 아래 왼
int dc[] = { 0,1,0,-1 };
int N, M, oil;
int minDis; //nextclient까지의 거리



int find(int sr, int sc, int ar, int ac){
    
    memset(visit, -1, sizeof(visit));		//시작점을 0 으로 구분표시하기위해 -1로 채워줌
    visit[sr][sc]=0;
    queue<pair<int, int>> q;
    q.push({sr,sc});
    
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        
        if(r == ar && c == ac) return visit[ar][ac] ;     //목적지면 return
        q.pop();
        for(int i=0; i<4; i++){
            int rr = r + dr[i];
            int cc = c + dc[i];
            
            if(rr < 0|| cc < 0 || rr >=N || cc >= N) continue;      //범위 넘어가면 pass
            if(visit[rr][cc] >=0) continue;       //가본곳이면 pass
            if(Map[rr][cc]) continue;   //벽있으면 pass
            
            visit[rr][cc] = visit[r][c] + 1;
            q.push({rr,cc});
        }
    }
    
    
    return visit[ar][ac]; 		//길을 못찾았으면 -1반환
}


int nextClient(int r, int c){
    int next = 999;
    int temp;
    int idx = -1;
    
    for(int i=0; i<M; i++){
        if(client[i][0]) continue;  //이미 태운적있으면 pass
        
        temp = find(r,c,client[i][1],client[i][2]);
        
        //temp가 더 적거나, 같은데 temp의 r이 더 적을때 next에 temp저장
        if(temp == -1) continue;
        if( temp < next || (temp == next && client[i][1] < client[idx][1] ) ){
            next = temp;
            idx = i;
        }else if(temp == next && client[i][1] == client[idx][1] ){      //행도 같을때
            
            if(client[i][2] < client[idx][2]){      //열 비교
                next = temp;
                idx =i;
            }
        }
    }
    
    minDis = next;
    return idx;
}


int main(void){
    //input
    cin >> N >> M >> oil;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> Map[i][j];
        }
    }
    
    int c,r;        //current position
    cin >> r >> c;
    c--;	//1부터시작이므로 배열에적용하기위해 1씩 빼준다
    r--;
    for(int i=0; i<M; i++){
        client[i][0] = 0;   //visited
        cin >> client[i][1] >> client[i][2] >> client[i][3] >> client[i][4];
        for(int j=1; j<5; j++){
            client[i][j] --; //배열적용1씩뺌
        }
    }
    
    
    
    int n, dis;
    for(int i=0; i<M; i++){			//승객수만큼 반복
        n = nextClient(r, c);		//다음승객의 idx받아옴
        if(n == -1){				
            cout << -1;
            return 0;
        }
        if(oil - minDis <= 0){
            cout << -1;
            return 0;
        }

        oil -= minDis;
        r = client[n][1];
        c = client[n][2];

        dis = find(r,c,client[n][3],client[n][4]);
        if(dis == -1){
            cout << -1;
            return 0;
        }
        if(oil - dis < 0){
            cout << -1;
            return 0;
            
        }
        oil += dis;
        r = client[n][3];
        c = client[n][4];
        client[n][0] = 1;

    }

    cout << oil;
    
    
    
    
}