(C++) - 백준(BOJ) 19238번 : 스타트 택시

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

19238번: 스타트 택시

구현 + bfs 문제였습니다.

 

풀이방법

 1. 입력 받은 후 손님의 데이터를 구조체를 이용해 벡터 형태로 저장합니다. 구조체는 손님의 출발 행,열 그리고 도착 행,열 그리고 택시까지의 거리로 이루어져 있습니다.

 

 2. 택시의 위치에서 각 지점의 거리를 계산해줍니다. 계산된 배열 dist를 확인하며 손님과 택시사이의 거리를 모두 갱신해줍니다. 최단 거리의 손님을 태우므로 이 경우에만 벡터를 조건에 따라 정렬해줍니다.

 

 3. 택시가 손님을 태우러 갑니다. 만약 손님을 태울 수 없다(연료부족)면 -1을 반환하며 이를 출력하고 프로그램을 종료합니다. 

제대로 이동할 수 있다면 그 만큼 연료를 줄입니다. 그 후 해당 손님이 있는 위치로 택시를 이동시킵니다.

 

 4. 다시 택시의 위치에서 각 지점의 거리를 계산합니다. 그 후 갱신하는 부분까지는 똑같으나 이미 손님을 태운 상태(option = 1) 이기 때문에 정렬하지 않습니다.

 

5. 택시가 목적지로 이동합니다. 만약 목적지까지 갈 연료가 부족하다면 -1을 반환합니다.

제대로 이동할 수 있다면 목적지까지의 거리만큼 연료를 줄입니다. 그 후 사용한 연료*2를 더해줍니다.

 

6. 2 ~ 5과정을 모든 손님을 태울때까지 반복합니다. 중간에 -1을 반환한 경우에는 -1을 출력 후 프로그램을 종료합니다.

 

7. fuel변수를 출력해줍니다.

 

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
using pii = pair<int,int>;
int n, m, fuel, ans;
int board[21][21], ck[21][21];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int taxiRow, taxiCol;
struct Customer { int startRow, startCol, endRow, endCol, distance; };
vector <Customer> customerInfo;
int dist[21][21];

bool cmp(Customer a, Customer b){
    if(a.distance == b.distance){
        if(a.startRow == b.startRow)
            return a.startCol < b.startCol;
        return a.startRow < b.startRow;
    }
    return a.distance < b.distance;
}

void updateDistance(){
    memset(ck,0,sizeof(ck));
    memset(dist,0,sizeof(dist));
    queue <pii> q;
    q.push({taxiRow,taxiCol});
    ck[taxiRow][taxiCol] = 1;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(1 > nx || nx > n || 1 > ny || ny > n) continue;
            if(board[nx][ny] == 1 || ck[nx][ny]) continue;
            ck[nx][ny] = 1;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx,ny});
        }
    }
}

void updateCustomerInfo(int option = 0){
    if(!option){
        for(int i = 0; i < customerInfo.size(); i++)
            customerInfo[i].distance = dist[customerInfo[i].startRow][customerInfo[i].startCol];
        sort(customerInfo.begin(),customerInfo.end(),cmp);
    }
    else{
        for(int i = 0; i < customerInfo.size(); i++)
            customerInfo[i].distance = dist[customerInfo[i].endRow][customerInfo[i].endCol];
    }
}

int goToDestination(int option = 0){
    updateDistance();
    if(!option) updateCustomerInfo();
    else updateCustomerInfo(1);
    
    if(!customerInfo[0].distance) {
        if(taxiRow != customerInfo[0].startRow || taxiCol != customerInfo[0].startCol)
            return -1;
    }
    if(customerInfo[0].distance > fuel) return -1;

    if(!option){
        taxiRow = customerInfo[0].startRow;
        taxiCol = customerInfo[0].startCol;
    }

    else{
        taxiRow = customerInfo[0].endRow;
        taxiCol = customerInfo[0].endCol;
    }

    
    fuel -= customerInfo[0].distance; 
    if(option == 1){
        fuel += customerInfo[0].distance * 2;
    }
    return 1;
}

int main(){
    cin >> n >> m >> fuel;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> board[i][j];
        }
    }
    cin >> taxiRow >> taxiCol;
    for(int i = 1; i <= m; i++){
        Customer customer;
        cin >> customer.startRow >> customer.startCol >> customer.endRow >> customer.endCol;
        customerInfo.push_back(customer);
    }
    while(customerInfo.size()){
        if(goToDestination() == -1){ cout << -1; return 0; }
        if(goToDestination(1) == -1){ cout << -1; return 0; };
        customerInfo.erase(customerInfo.begin());
    }
    cout << fuel;
}

 

Test Case

질문 게시판의 반례를 가져왔습니다.

 

input

4 2 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
3 1
1 1 1 2
1 2 3 2
답 : 4
    

input

2 1 1
0 0
0 0
2 2
2 2 2 1

답 2

 

input

5 5 4
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 3
2 2 4 2
4 2 4 4
4 4 2 4
2 4 2 2
2 5 3 3

답 10