BOJ 19238 스타트 택시

www.acmicpc.net/problem/19238

 

문제 해결 전략

택시 위치에서 큐 돌리면서 사람을 찾는다.

사람을 찾으면 우선순위 큐에 넣는다. 우선순위 큐에 넣는 이유는 사람들을 다 찾고, 그 중에

조건에 가장 적합한 원소만 뽑아주기 때문이다. 또한,

택시 위치가 사람의 위치와 같이 시작하는 경우, 다른 사람의 위치가 또 다른 사람의 목적지에 위치하는 경우 등을

고려하여 문제를 풀어야 한다.

 

소스

소스는 위에서 설명하지 못한 부분을 최대한 코드 위에 주석 처리 하였다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define endl "\n"
#define MAX 21
const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
int map[MAX][MAX];
int n, m, f;
struct POS {
    int y, x;
};
struct POSS {
    int y, x, fuel;
};
POS person[MAX*MAX];
POS dst[MAX*MAX];
POSS taxi;
int personNum;
// 입력 받기
void input() {
    cin >> n >> m >> f;
    taxi.fuel = f;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) {
                map[i][j] = -1;
            }
        }
    }
    cin >> taxi.y >> taxi.x;
    for(int i = 1; i <= m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        person[i].y = a; person[i].x = b;
        dst[i].y = c; dst[i].x = d;
        personNum++;
        map[person[i].y][person[i].x] = i;
    }
}
// 현재 위치에서 목적지까지 거리 구하기
int getDstNum(int y, int x, int dstY, int dstX) {
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {y, x}});
    bool check[MAX][MAX];
    check[y][x] = true;
    memset(check, 0, sizeof(check));
    while(!q.empty()) {
        int d = q.front().first;
        int yy = q.front().second.first;
        int xx = q.front().second.second;
        q.pop();
        // 큐 돌리다 현재 위치가 목적지 위치와 같다면 d(거리) 리턴
        if(yy == dstY && xx == dstX) {
            return d;
        }
        for(int i = 0; i < 4; i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if(ny < 1 || ny > n || nx < 1 || nx > n) continue;
            if(map[ny][nx] == -1 || check[ny][nx]) continue;
            q.push({d + 1, {ny, nx}});
            check[ny][nx] = true;
        }
    }
    // 목적지에 도달할 수 없다면 -1 리턴
    return -1;
}
void solution() {
    while(1) {
        if (personNum == 0) {
            cout << taxi.fuel << endl;
            break;
        }
        // 초기화
        queue<pair<int, pair<int, int>>> q;
        priority_queue< pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, 
        greater<pair<int, pair<int, int>>> > pq;
        bool check[MAX][MAX];
        memset(check, 0, sizeof(check));
        check[taxi.y][taxi.x] = true;
        q.push({0, {taxi.y, taxi.x}});
        cout << "초기 택시 위치 taxi.y = " << taxi.y << " taxi.x = " << taxi.x << " taxi.fule = " << taxi.fuel << endl;
        bool sw = false;
        // 택시에서 사람들까지 거리 구하고 우선순위 큐에 넣어주기.
        // 택시와 초기 사람의 위치가 같은 경우 따로 계산하기.
        for(int i = 1; i <= m; i++) {
            if(taxi.y == person[i].y && taxi.x == person[i].x && map[person[i].y][person[i].x]) {
                cout << "초기 위치에 사람이 존재하는 경우" << endl;
                pq.push({0, {person[i].y, person[i].x}});
                break;
            }
        }
        // 큐 돌리면서 사람 찾기
        while(!q.empty()) {
            int d = q.front().first;
            int y = q.front().second.first;
            int x = q.front().second.second;
            q.pop();
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(ny < 1 || ny > n || nx < 1 || nx > n) continue;
                if(map[ny][nx] == -1 || check[ny][nx]) continue;
                // 만약 사람이 존재 한다면, 우선 순위 큐에 넣기
                if(map[ny][nx]) {
                    pq.push({d + 1, {ny, nx}});
                    sw = true;
                }
                q.push({d + 1, {ny, nx}});
                check[ny][nx] = true;
            }
        }
        // 큐를 돌면서 사람을 찾지 못 했고, 택시가 출발 위치에도 사람이 없는 경우(pq.empty() == true)
        if(sw == false && pq.empty() == true) {
            cout << -1 << endl;
            break;
        }
        // 우선 순위 큐에서 처음으로 나온 원소는 조건에 가장 최적의 사람이다.
        // 택시를 사람 위치로 바꿔주기.
        cout << "목직지 사람 위치와 연료(비용) = " << pq.top().second.first << " " << pq.top().second.second << " / " << pq.top().first<< endl;
        taxi.fuel -= pq.top().first;
        taxi.y = pq.top().second.first;
        taxi.x = pq.top().second.second;
        cout << "사람 태운 후 택시 연료 = " << taxi.fuel << endl;
        if(taxi.fuel < 0) {
            cout << "사람 태운 후 택시 연료가 마이너스일 때" << endl;
            cout << -1 << endl;
        }
        // 택시에서 목적지까지 위치 구해주기.
        int dstNum = getDstNum(taxi.y, taxi.x, dst[map[taxi.y][taxi.x]].y, dst[map[taxi.y][taxi.x]].x);
        int newY = dst[map[taxi.y][taxi.x]].y;
        int newX = dst[map[taxi.y][taxi.x]].x;
        cout << "목직지 위치 = " << newY << " " << newX << " dstNum = " << dstNum << endl;
        if(taxi.fuel - dstNum >= 0 && dstNum > 0) {
            taxi.fuel -= dstNum;
            taxi.fuel += dstNum*2;
            taxi.y = newY;
            taxi.x = newX;
        } else {
            cout << -1 << endl;
            break;
        }
        cout << "목적지까지 간 후 택시 연료 = " << taxi.fuel << endl;
        // 사람 live false로 만들기.
        map[pq.top().second.first][pq.top().second.second] = 0;
        personNum--;
    }


}
void solve() {
    input();
    solution();
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    freopen("sample_input.txt", "r", stdin);
    solve();
}