[Baekjoon][19238] 스타트 택시

출처 - 백준사이트

19238. 스타트 택시

나의 풀이

해당 문제는 어렵지는 않은데 문제에 함정이 있는 걸 조심해야한다.
나는 처음에 풀때, 손님들의 출발지는 모두다 다르고 목적지도 모두다 다르다고 이해하여 문제를 풀었다가,
계속 틀려서, 문제를 자세히 보니까 손님들의 출발지는 모두 다르지만 목적지는 같을 수 있다는 것을 파악했다.
또한, 손님A의 출발지가 손님B의 목적지가 될수도 있다는 사실에 주의하여야 한다.
그래서.. 난.. 코드를 처음부터 다시 짜게 되었다고 한다....

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

#define MAX_SIZE    20

using namespace std;

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};

typedef struct {
    pair<int, int> departures;
    pair<int, int> arrivals;
} People;

int N, M, Fuel;
bool is_fuel_zero = false;
pair<int,int> taxi;
vector<People> people;
int map[MAX_SIZE][MAX_SIZE];

bool vector_compare(People front, People back) {
    if (front.departures.first < back.departures.first)
        return true;
    else if (front.departures.first == back.departures.first) {
        if (front.departures.second < back.departures.second)
            return true;
        else
            return false;
    }
    else
        return false;
}

int FindStart() {
    vector<pair<int,int>> v;
    bool visit[MAX_SIZE][MAX_SIZE];
    memset(visit, false, sizeof(visit));

    v.emplace_back(make_pair(taxi.first, taxi.second));
    visit[taxi.first][taxi.second] = true;
    taxi.first = -1, taxi.second = -1;

    while (!v.empty()) {
        for (int idx = 0; idx < people.size() ; idx++) {
            pair<int,int> temp = people[idx].departures;

            for (int v_idx = 0 ; v_idx < v.size() ; v_idx++) {
                if (v[v_idx].first == temp.first && v[v_idx].second == temp.second)
                    return idx;
            }
        }

        vector<pair<int, int>> cycle = v;
        v.clear();

        while (!cycle.empty()) {
            pair<int, int> temp = cycle.back();
            cycle.pop_back();

            for (int idx = 0 ; idx < 4 ; idx++) {
                int ny = temp.first + dy[idx];
                int nx = temp.second + dx[idx];

                if (0 <= ny && ny < N && 0 <= nx && nx < N && map[ny][nx] != 1 && !visit[ny][nx]) {
                    visit[ny][nx] = true;
                    v.emplace_back(make_pair(ny,nx));
                }
            }
        }

        Fuel--;
    }

    return -1;
}

void FindEnd(int people_idx) {
    vector<pair<int,int>> v;
    bool visit[MAX_SIZE][MAX_SIZE];
    memset(visit, false, sizeof(visit));

    v.emplace_back(make_pair(people[people_idx].departures.first, people[people_idx].departures.second));
    visit[people[people_idx].departures.first][people[people_idx].departures.second] = true;

    int fy = people[people_idx].arrivals.first;
    int fx = people[people_idx].arrivals.second;

    vector<People>::iterator itr = people.begin() + people_idx;
    people.erase(itr);

    int cycle_cnt = 0;
    while (!v.empty()) {
        vector<pair<int, int>> cycle = v;
        v.clear();

        for (int idx = 0 ; idx < cycle.size() ; idx++) {
            if (cycle[idx].first == fy && cycle[idx].second == fx) {
                Fuel += (cycle_cnt*2);
                taxi = {cycle[idx].first, cycle[idx].second};
                return;
            }
        }

        if (Fuel == 0)
            break;

        while (!cycle.empty()) {
            pair<int, int> temp = cycle.back();
            cycle.pop_back();

            for (int idx = 0 ; idx < 4 ; idx++) {
                int ny = temp.first + dy[idx];
                int nx = temp.second + dx[idx];

                if (0 <= ny && ny < N && 0 <= nx && nx < N && map[ny][nx] != 1 && !visit[ny][nx]) {
                    visit[ny][nx] = true;
                    v.emplace_back(make_pair(ny,nx));
                }
            }
        }

        Fuel--;
        cycle_cnt++;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> N >> M >> Fuel;

    for (int y = 0 ; y < N ; y++) {
        for (int x = 0 ; x < N ; x++)
            cin >> map[y][x];
    }

    cin >> taxi.first >> taxi.second;
    taxi.first -= 1, taxi.second -= 1;

    for (int idx = 0; idx < M ; idx++) {
        People p;

        cin >> p.departures.first >> p.departures.second >> p.arrivals.first >> p.arrivals.second;
        p.departures.first--;
        p.departures.second--;
        p.arrivals.first--;
        p.arrivals.second--;

        people.push_back(p);
    }

    sort(people.begin(), people.end(), vector_compare);

    while (Fuel != 0) {
        int departure_idx = FindStart();

        if (departure_idx != -1)
            FindEnd(departure_idx);

        if (people.empty())
            break;
    }

    (Fuel != 0) ? cout << Fuel : cout << -1;

    return 0;
}