19238번-스타트택시

문제

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

19238번: 스타트 택시

---

접근방법

1) 접근 사고

1. 내가 태울 승객을 BFS 탐색으로 정한다, 이때 소모한 가스값은 갱신해준다.

2. 태울 승객의 위치에서 도착지까지 BFS 탐색을 한다, 이때 소모한 가스값은 갱신해준다.

 

2) 시간 복잡도

O(V + E)

 

3) 배운 점

여러 번 시도한 문제이다. 테스트 케이스는 다 통과하나 문제가 자꾸 틀렸습니다가 나와서 힘들었다 이에 대해서 안 좋은 습관을 찾았고 글을 따로 작성했다.

https://hyeophyeop.tistory.com/106

BFS, DFS 탐색 팁

안 좋은 습관을 가지고 있어서 나중에 똑같은 실수를 저지를까 봐 따로 정리했다.

 

4) PS

디버깅 그만 하고 싶다...

---

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
const int MAX = 21;
int my[] = {-1,0,1,0};
int mx[] = {0,-1,0,1};
 
struct Car{
    int y, x, gas;
};
 
bool operator < (const Car &a, const Car &b){
    if(a.gas != b.gas){
        return a.gas < b.gas;
    }
    if(a.y != b.y){
        return a.y > b.y;
    }
    if(a.x != b.x){
        return a.x > b.x;
    }
    return false;
}
 
struct drive{
    int n, m, k;
    int board[MAX][MAX];
    Car car;
    drive(int n, int m, int k) : n(n), m(m), k(k) {}
    tuple<int,int,int,int> cityzen[401];
    bool visited[MAX][MAX];
    int fNum;
 
    bool isValid(int y, int x){
        return (y >= 0 && y < n && x >= 0 && x < n);
    }
 
    void init(){
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < n; j++){
                cin >> board[i][j];
                if(board[i][j] == 1)
                    board[i][j] = -1;
            }
        }
        cin >> car.y >> car.x;
        car.gas = k;
        car.y--, car.x--;
        for(int i = 1; i <= m; i++){
            int sy, sx, ey, ex;
            cin >> sy >> sx >> ey >> ex;
            sy--, sx--, ey--, ex--;
            board[sy][sx] = i;
            cityzen[i] = {sy, sx, ey, ex};
        }
    }
 
    bool find_BFS(){
        priority_queue<Car> pq;
        pq.push({car.y, car.x, car.gas});
        visited[car.y][car.x] = true;
        memset(visited, false, sizeof visited);
 
        int cnt = 0;
        while(!pq.empty()){
            int pqSize = pq.size();
 
            for(int i = 0; i < pqSize; i++){
                auto[y, x, gas] = pq.top();
                pq.pop();
 
                if(board[y][x] > 0){
                    if(gas >= 0){
                        car.y = y;
                        car.x = x;
                        car.gas = gas;
                        fNum = board[y][x];
                        return true;
                    }
                    else
                        return false;
                }
                for(int d = 0; d < 4; d++){
                    int ny = y + my[d];
                    int nx = x + mx[d];
                    if(isValid(ny, nx)){
                        if(!visited[ny][nx] && board[ny][nx] != -1){
                            pq.push({ny, nx, gas - 1});
                            visited[ny][nx] = true;
                        }
                    }
                }
            }
            cnt++;
        }
        return false;
    }
 
    bool goal_BFS(){
        memset(visited, false, sizeof visited);
        queue<pair<int,int>> q;
        q.push({car.y, car.x});
        visited[car.y][car.x] = true;
        auto[sy, sx, ey, ex] = cityzen[fNum];
        int cnt = 0;
 
        while(!q.empty()){
            int qSize = q.size();
            for(int i =  0; i < qSize; i++){
                auto[y, x] = q.front();
                q.pop();
                if(y == ey && x == ex){
                    car.gas -= cnt;
                    if(car.gas >= 0){
                        car.gas += cnt * 2;
                        car.y = ey;
                        car.x = ex;
                        board[sy][sx] = 0;
                        return true;
                    } else{
                        return false;
                    }
                }
                for(int d = 0; d < 4; d++){
                    int ny = y + my[d];
                    int nx = x + mx[d];
                    if(isValid(ny, nx)){
                        if(!visited[ny][nx] && board[ny][nx] != -1){
                            q.push({ny, nx});
                            visited[ny][nx] = true;
                        }
                    }
                }
            }
            cnt++;
        }
        return false;
    }
 
    void printBoard(){
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < n; j++){
                cout << board[i][j] <<" ";
            }
            cout <<"\n";
        }
        cout <<"========board========" <<"\n";
    }
};
 
int main(){
    int n, m, k;
    cin >> n >> m >> k;
    drive op(n,m,k);
    op.init();
    //op.printBoard();
    for(int i = 0; i < m; i++){
        if(!op.find_BFS()){
            cout << "-1" <<"\n";
            return 0;
        }
        if(!op.goal_BFS()){
            cout << "-1" <<"\n";
            return 0;
        }
    }
    cout << op.car.gas << "\n";
}