[백준 19238]스타트 택시

Junghyun(Alec) Park·2021년 9월 26일
0

BAEKJOON

목록 보기
1/13

A. 접근법

1)택시가 가장 가까운 승객을 고르고, 2)승객이 정해진 목적지로 가는 거리를 계산해야하는 문제이기 때문에 BFS를 이용한 탐색을 각각 두번 적용하여 문제를 해결하였습니다.

2번의 거리를 BFS로 구했을 때 이는 고정 값으로 택시가 이동해도 손님과 목적지 사이 거리는 변함이 없기 때문에 이는 한 번만 계산을 하면 됩니다. 손님과 목적지 사이의 거리를 불필요하게 계속 구했기 때문에 시간 초과가 발생하기도 했습니다.

B. 구현

택시가 가장 가까운 승객을 고를 때 가장 가까운 거리가 동일하면 행 번호가 작은 승객, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고르게 되어있다. 처음에는 BFS의 큐에 넣을 때 이 순으로 넣어만 주면 먼저 선택되는 손님이 해당 조건에 맞는 손님이라고 착각하였습니다. 하지만 이렇게 BFS 탐색을 하면 잘못된 손님을 선택하게 될 수도 있습니다.

손님는 G1 3행 5열, 손님 G2는 4행 2열에 위치한다고 가정합니다. 표의 숫자는 '(택시와의 거리)-(탐색 순서)'입니다. G1, G2는 모두 거리가 2이지만 문제 조건 상 G1이 선택되어야 하지만 잘못된 BFS 탐색을 구현하면 G2가 선택되게 됩니다. 따라서 문제가 제시한 조건을 그대로 동일한 거리가 여러명이면 먼저 후보자들을 다 구해 놓은 후 행과 열의 우선순위를 따라서 손님을 선택해야합니다.

C. 코드

#include <iostream>
#include <vector>

using namespace std;

int T, N, M;
int gas;
vector<vector<int>> table;
vector<vector<int>> guest;
vector<int> taxi;
int idx = 0;

int valid(int x, int y, vector<vector<int>>& v) {
    if(x < 0 || x >= N || y < 0 || y >= N)
        return 0;
    if(v[x][y] == 0 && table[x][y] == 0) {
        v[x][y] = 1;

        return 1;
    }
    else
        return 0;
}

int bfs(int a, int b, int c, int d, vector<vector<int>>& q, vector<vector<int>>& visit, int stage) {

    if(stage == -1) {
        vector<int> p(2, 0);
        p[0] = a;
        p[1] = b;

        q.push_back(p);
        visit.resize(N);
        for(auto it = visit.begin(); it != visit.end(); it++)
            it->resize(N);
        visit[a][b] = 1;

        return bfs(a, b, c, d, q, visit, stage + 1);
    }
    else {
        int size = q.size();
        if(size == 0)
            return -1;
        for(int i = 0; i < size; i++) {
            int x = q[0][0];
            int y = q[0][1];
            q.erase(q.begin());
            if(x == c && y == d)
                return stage;
            
            else {
                if(valid(x - 1, y, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x - 1;
                    t[1] = y;
                    q.push_back(t);
                }
                if(valid(x, y - 1, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x;
                    t[1] = y - 1;
                    q.push_back(t);
                }
                if(valid(x, y + 1, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x;
                    t[1] = y + 1;
                    q.push_back(t);
                }
                if(valid(x + 1, y, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x + 1;
                    t[1] = y;
                    q.push_back(t);
                }
            }
        }
        return bfs(a, b, c, d, q, visit, stage + 1);
    }
}
int taxi_bfs(int a, int b, int c, int d, vector<vector<int>>& q, vector<vector<int>>& visit, int stage, int& idx) {

    if(stage == -1) {
        vector<int> p(2, 0);
        p[0] = a;
        p[1] = b;

        q.push_back(p);
        visit.resize(N);
        for(auto it = visit.begin(); it != visit.end(); it++)
            it->resize(N);
        visit[a][b] = 1;

        return taxi_bfs(a, b, c, d, q, visit, stage + 1, idx);
    }
    else {
        int size = q.size();
        if(size == 0)
            return -1;
        for(int i = 0; i < size; i++) {
            int x = q[0][0];
            int y = q[0][1];
            q.erase(q.begin());
            
            for(int j = 0; j < guest.size(); j++) {
                if(x == guest[j][0] && y == guest[j][1]) {
                    if(idx == -1)
                        idx = j;
                    else {
                        int px = guest[idx][0];
                        int py = guest[idx][1];
                        int cx = guest[j][0];
                        int cy = guest[j][1];

                        if(cx < px) {
                            idx = j;
                        }
                        else if(cx == px) {
                            if(cy < py)
                                idx = j;
                        }
                        else {}
                    }
                }
            }

            //else {
            if(idx == -1) {
                if(valid(x - 1, y, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x - 1;
                    t[1] = y;
                    q.push_back(t);
                }
                if(valid(x, y - 1, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x;
                    t[1] = y - 1;
                    q.push_back(t);
                }
                if(valid(x, y + 1, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x;
                    t[1] = y + 1;
                    q.push_back(t);
                }
                if(valid(x + 1, y, visit)) {
                    vector<int> t(2, 0);
                    t[0] = x + 1;
                    t[1] = y;
                    q.push_back(t);
                }
                //}
            }
        }
        if(idx != -1)
            return stage;
        return taxi_bfs(a, b, c, d, q, visit, stage + 1, idx);
    }
}
void solver() {
    int i, j;
    //int idx = -1;
    idx = -1;
    int route = 999999999;
    int tRoute;
   int nog = guest.size();
    if(nog == 0)
        return;

    vector<vector<int>> q;
    vector<vector<int>> visit;
    route = taxi_bfs(taxi[0], taxi[1], 0, 0, q, visit, -1, idx);
    
    if(idx == -1) {
        gas = -1;
        return;
    }
    // go to guest
    gas -= route;
    if(gas < 0) {
        gas = -1;
        return;
    }

    int gx, gy;
    tRoute = guest[idx][4];

    if(tRoute == -1) {
        gas = -1;
        return;
    }
    else {
        gas -= tRoute;
        if(gas < 0) {
            gas = -1;
            return;
        }
        else {
            gas += 2 * tRoute;
            taxi[0] = guest[idx][2];
            taxi[1] = guest[idx][3];
            guest.erase(guest.begin() + idx);
        }
    }
    solver();

}
int main() {

    T = 1;
    int i, j;
    for(int tc = 0; tc < T; tc++) {
        int tmp;
        scanf("%d %d %d", &N, &M, &gas);
        table.resize(N);
        //taxi.resize(2);
        //guest.resize(M);
        guest.clear();
        for(i = 0; i < N; i++) {
            table[i].resize(N);
            for(j = 0; j < N; j++) {
                scanf("%d", &tmp);
                table[i][j] = tmp;
            }

        }
        taxi.resize(2);
        scanf("%d", &tmp);
        taxi[0] = tmp - 1;
        scanf("%d", &tmp);
        taxi[1] = tmp - 1;
        
        for(i = 0; i < M; i++) {
            vector<int> tv(5,0);
            scanf("%d %d %d %d", &tv[0], &tv[1], &tv[2], &tv[3]);
        
            tv[0]--;
            tv[1]--;
            tv[2]--;
            tv[3]--;
            tv[4] = 0;
            vector<vector<int>> q3;
            vector<vector<int>> visit3;
            tv[4] = bfs(tv[0], tv[1], tv[2], tv[3], q3, visit3, -1);
            guest.push_back(tv);
            
        }

        solver();
        printf("%d\n", gas);

    }
    return 0;
}

D. 결과

profile
박정현입니다

0개의 댓글