스타트 택시

• 문제

www.acmicpc.net/problem/19238

19238번: 스타트 택시

• 내 코드

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<int>> m;
unordered_map<int, vector<int>> idx_dst;

int N, M, O;
int t_r, t_c;
int mv[4][2] = {
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};


void printMap(vector<vector<int>> m){
    for(int i=0; i<m.size(); i++){
        for(int j=0; j<m.size(); j++){
            cout << m[i][j] << ' ';
        }
        cout << '\n';
    }
}

void printIdxDst(unordered_map<int, vector<int>> idx_dst){
    for(auto iter=idx_dst.begin(); iter != idx_dst.end(); iter++){
        cout << iter->first << " : (" << (iter->second)[0] << ", " << (iter->second)[1] << ")\n";
    }
}

void printPair(pair<pair<int,int>,int> p){
    cout << "{{" << p.first.first << ", " << p.first.second << "}, " << p.second << "}\n";
}

int findPassenger(int s_r, int s_c){
    queue<pair<pair<int,int>,int>> q;
    bool his[N][N];

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            his[i][j] = false;
        }
    }
    
    int p_idx = 2e9; int p_r = N; int p_c = N; int p_d = 2e9;
    //현재 자리에 승객이 있어
    if(m[s_r][s_c] != 0){
        p_idx = m[s_r][s_c];
        p_d = 0;
        p_r = t_r;
        p_c = t_c;
    }else{
    //그렇지 않으면 찾아야함
        q.push({{s_r,s_c}, 0});
        his[s_r][s_c] =  true;
        while(!q.empty()){
            auto cur_node = q.front();
            q.pop();
            int c_r = cur_node.first.first;
            int c_c = cur_node.first.second;
            int c_d = cur_node.second;
            //printPair(cur_node);
            if(m[c_r][c_c] != 0){
                if(p_d > c_d){
                    p_idx = m[c_r][c_c];
                    p_r = c_r;
                    p_c = c_c;
                    p_d = c_d;
                }else if(p_d == c_d){
                    if(p_r == c_r){
                        if(p_c > c_c){
                            p_idx = m[c_r][c_c];
                            p_r = c_r;
                            p_c = c_c;
                            p_d = c_d;
                        }
                    }else if(p_r > c_r){
                        p_idx = m[c_r][c_c];
                        p_r = c_r;
                        p_c = c_c;
                        p_d = c_d;
                    }
                }
                continue;
            }

            for(int i=0; i<4; i++){
                int n_r = c_r + mv[i][0];
                int n_c = c_c + mv[i][1];
                int n_d = c_d+1;
                if(N <= n_r || n_r < 0 || N <= n_c || n_c < 0){
                    continue;
                }else if(m[n_r][n_c] == 1){
                    continue;
                }else if(his[n_r][n_c]){
                    continue;
                }
                q.push({{n_r, n_c}, n_d});
                his[n_r][n_c] = true;
            }
        }

    }

    if(idx_dst.find(p_idx) == idx_dst.end()){
        //cout << "can't find passenger\n";
        return -1;
    }else if(O - p_d < 0){
        //cout << "out of fuel\n";
        //cout << "(" << p_r << ", " << p_c << ", " << p_d << ")\n";
        return -1;
    }else{
        O -= p_d;
        vector<int> coord = idx_dst[p_idx];
        //cout << "idx_dst[" << p_idx << "] = {" << coord[0] << ", " << coord[1] << "}\n";
        t_r = p_r; t_c = p_c;
        m[p_r][p_c] = 0;
        return p_idx;
    }


}

int goDst(int p_idx){

    vector<int> coord = idx_dst[p_idx];
    int d_r = coord[0]; int d_c = coord[1];
    int min_d = 2e9;

    queue<pair<pair<int,int>,int>> q;
    bool his[N][N];

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            his[i][j] = false;
        }
    }


    q.push({{t_r, t_c}, 0});
    his[t_r][t_c] = true;

    while(!q.empty()){
        auto cur_node = q.front();
        q.pop();
        int c_r = cur_node.first.first;
        int c_c = cur_node.first.second;
        int c_d = cur_node.second;

        if(d_r == c_r && d_c == c_c){
            min_d = min(min_d, c_d);
            continue;
        }

        for(int i=0; i<4; i++){
            int n_r = c_r + mv[i][0];
            int n_c = c_c + mv[i][1];
            int n_d = c_d+1;
            if(N <= n_r || n_r < 0 || N <= n_c || n_c < 0){
                continue;
            }else if(m[n_r][n_c] == 1){
                continue;
            }else if(his[n_r][n_c]){
                continue;
            }
            q.push({{n_r, n_c}, n_d});
            his[n_r][n_c] = true;
        }
    }

    if(min_d == 2e9){
        //cout << "can't find dest\n";
        return -1;
    }else if(O-min_d < 0){
        //cout << "out of fuel while going to dst\n";
        return -1;
    }else{
        O += min_d;
        t_r = d_r; t_c=d_c;
        return 1;
    }

}

int main(){

    cin >> N >> M >> O;


    for(int i=0; i<N; i++){
        vector<int> row;
        int input;
        for(int j=0; j<N; j++){
            cin >> input;
            row.push_back(input);
        }
        m.push_back(row);
    }

    cin >> t_r >> t_c;
    t_r -= 1; t_c -= 1;

    for(int i=1; i<=M; i++){
        int cur_idx = i+10;
        int s_r,s_c,e_r,e_c;
        cin >> s_r >> s_c >> e_r >> e_c;
        m[s_r-1][s_c-1] = cur_idx;
        idx_dst[cur_idx] = vector<int>{e_r-1, e_c-1};

    }
    //cout << t_r << ", " << t_c << '\n';

    int pC = M;
    //cout << "start ---------------\n";
    while(true){
        int curPIdx= findPassenger(t_r,t_c);
        if(curPIdx == -1)
            break;
        //cout << "Oil : " << O << '\n';
        //cout << t_r << ", " << t_c << '\n';

        if(goDst(curPIdx) == -1)
            break;
        //cout << "Oil : " << O << '\n';
        //cout << t_r << ", " << t_c << '\n';
        //cout << "=====================\n";
        pC--;
    }
    if(pC == 0)
        cout << O << '\n';
    else
        cout << -1 << '\n';


}

• 반성

1시간 40분 걸림... 더 빨리 풀 수 있었음

코드 짤 때 배열 범위나 Map의 key에 없을 것 같은 값은 미리 예외처리를 하거나 고려를 좀 하고 짜자