[ 백준 19238 ] 스타트 택시 (C++)

백준의 스타트 택시(19238) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

먼저 문제에서 핵심인 손님에 대해서 정리를 하고 본격적인 문제 풀이에 들어가보자.

이 문제에서 우리가 알아야 할 손님에 대한 정보는 뭐가 있을지 생각을 해보자.

굉장히 간단하게도 우리가 손님에 대해 알아야 할 정보는 "손님의 위치 & 손님의 목적지 위치" 만 알고 있으면 된다.

그래서 본인은 위의 4가지 정보 (손님의 위치 x, y좌표 , 손님의 목적지 위치 x, y좌표) 를 구조체로 만들어서 손님을 관리해 주었다.

손님의 번호는 1번부터 M번까지로 설정해 주었고, 이 손님의 번호를 맵에서 표시해 주었다.

그런데 ! 이렇게 맵에 표시해주기 위해서는 맵의 변형이 약간 필요하다. 왜냐하면 주어지는 맵에서는 '1'이 움직일 수 없는 벽이 있는 위치로 주어지기 때문이다. 그런데 ? 손님의 번호는 1번부터 이기 때문에 이대로 1번 손님을 맵에서 그대로 '1'로 표현해 주게 되면 이게 1번 손님인지 벽인지 판단할 수 없기 때문이다. 그래서, 본인은 주어지는 맵에서 벽이 있는 위치는 '1'이 아닌 '-1'로 바꿔서 저장해 주었다. 그리고 손님이 있는 위치는 손님의 번호대로 저장해 주었다.

문제에서 설명으로 주어진 그림을(예제입력1) 본인이 생각한 맵으로 표현해보면 다음과 같다.

.

위와 같이 맵을 약간 변형해서 저장해 주었다.

 

본인은 먼저 크게 2가지 파트로 나누어서 구현해 보았다.

1. 현재 택시 위치로 부터, '조건에 맞는' 가장 가까운 손님 찾기

2. 손님을 목적지까지 이동시키기

이렇게 2가지로 나눠보았다.

 

1. 현재 택시 위치로 부터, '조건에 맞는' 가장 가까운 손님 찾기

현재 택시 위치로부터 조건에 맞는 가장 가까운 손님을 찾아야 한다는 것이다. 이 과정에서 본인은 너비우선탐색(BFS)을 이용해서 가장 가까운 손님을 찾아주었다. 물론, 이 과정에서 무작정 가까운 손님을 찾는 것이 아닌, 현재 남은 연료의 양을 계산해 가면서

"남은 연료의 양으로 찾아갈 수 있는 손님들 중, 조건에 맞는 가장 가까운 손님"을 찾아 주었다.

그런데 문제에서도 말했듯이, 단순 거리만 비교했을 때는 가까운 손님이 여러명일 수가 있다.

그래서 본인은 BFS로 탐색을 진행하면서 "현재 연료로 찾아갈 수 있는 손님들"에 대한 정보를 하나의 vector를 선언해 저장해 주었다. 그럼 예를들어서 현재 택시의 위치에서, 남은 연료로 a번 손님, b번 손님, c번 손님에게 갈 수 있다고 가정해보자.

그럼 여기서 우리는 어떤 손님을 선택해줘야할까 ?? 문제에서 제시한 조건처럼,

1. 거리가 가까운 사람일 수록 가장 우선적으로 선택

2. 1번이 여러명일 경우, 행이 가장 작은 사람이 우선적으로 선택

3. 2번이 여러명일 경우, 열이 가장 작은 사람이 우선적으로 선택 되어야 한다.

그럼 "현재 연료로 갈 수 있는 손님들"을 Vector에 저장해주었다고 했는데, 이 Vector에서는 어떤 정보를 가지고 있어야할까 ??

1. 거리에 대한 정보를 가지고 있어야 한다. 왜냐하면 손님을 선택하는 가장 첫 번째 조건이기 때문이다.

2. 행에 대한 정보를 가지고 있어야 한다. 손님을 선택하는 두 번째 조건이기 때문이다.

3. 열에 대한 정보를 가지고 있어야 한다. 손님을 선택하는 최종적인 조건이기 때문이다.

4. 손님의 번호를 가지고 있어야 한다. 손님의 번호는 왜 가지고 있어야 할까 ? 위의 3가지 조건으로 어떤 한 명의 손님이 선택되었다고 가정해보자. 그럼 결과적으로 그 손님이 몇 번 손님인지는 우리가 알고 있어야 한다. 왜냐하면, 해당 손님의 목적지로 이동시켜 주어야 하기 때문이다. 그래서 본인은 Vector에서 관리할 만한 정보들을 구조체로 만들어 주었다.

이 구조체가 가지고 있는 멤버변수는 위에서 말한 정보들이 있다.

[ 거리 , x좌표 , y좌표 , 손님의 번호 ] 이렇게 4가지 멤버변수를 가지는 구조체를, 위에서 말한 Vector에서 관리하는 자료형으로

선언해 주었다.

그럼 ! 현재 가진 연료로 손님을 찾기 위해서 BFS탐색을 모두 진행했을 때, 그 결과 Vector의 크기가 0이라는 것은 무엇을 의미할까?? "현재 연료로는 손님을 찾아갈 수 없다" 라는 것을 의미한다. 즉 ! 문제에서 제시한 '-1'을 출력해야 하는 첫 번째 조건이다.

만약, Vector의 크기가 0이 아니라면, 해당 Vector를 위에서 말한 조건대로 정렬시켜주고, 정렬 결과 Vector의 0번 Index에 있는 손님을 목적지까지 옮겨주면 된다.

 

2. 손님을 목적지 까지 이동시키기

1번 과정을 통해서 몇 번 손님을 이동시켜야 할지 판단했다면, 이제 이 손님을 목적지까지 이동시켜 주면 된다. 물론 ! 이 과정에서도 연료가 바닥나게 되면 이동시켜 줄 수 없게되고, 문제에서 제시한 '-1'을 출력해야 하는 두 번째 조건이 여기에 해당한다.

손님을 이동시켜 주는 이 과정에서도 BFS를 사용해주었다. 마찬가지로 남은 연료의 양을 체크해주면서 탐색을 진행해 주었다. 연료가 더 이상 부족해서 갈 수 없다면 -1을 출력하도록 해 주었고, 갈 수 있다면 연료의 양을 문제에서 제시한 대로 설정해 주었다.

 

이 문제에서 본인은 2가지 파트로 나누고 2가지 파트에서 모두 BFS를 사용했는데 BFS탐색하는 과정에 대해서 간단하게만 이야기 하겠다. 2파트 모두 BFS에서 사용되는 Queue에서 4개의 변수를 관리해주었다.

모두 [ x좌표 , y좌표 , 움직인 거리 , 남은 연료의 양 ] 이렇게 4개의 변수를 관리해 주었다.

1번 파트 즉, 현재 택시의 위치에서 손님을 찾을 때는 초기값이 [ 택시의 x좌표, 택시의 y좌표, 움직인 거리, 남은 연료의 양 ]이 되고, 한 칸 한 칸 움직일 때 마다, 움직인 거리는 + 1이 되는 반면, 남은 연료의 양은 -1씩 해주면서 탐색을 진행해 주었다.

2번 파트 즉, 손님을 목적지까지 이동시키는 부분에서는, 초기값이 [ 손님의 x좌표, 손님의 y좌표, 움직인 거리, 남은 연료의 양 ] 이 되고, 마찬 가지로, 한 칸 움직일 때 마다, 움직인 거리는 + 1이 되고, 남은 연료의 양은 -1씩 해주면서 탐색을 진행해 주었다.

만약 ! 중간에 탐색을 진행하다가 남은 연료의 양이 0이 되었다는 것은 ? 택시가 더 이상 움직일 수 없음을 뜻하고, 손님을 더 이상 이동시킬 수 없기 때문에 -1을 출력하도록 구현해 주었다.

 

[ 소스코드 ]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
/* 손님을 관리하기 위한 구조체 */
/* 알아야할 정보 = [ 손님의 좌표 , 손님의 목적지 좌표 ] */
struct CUSTOMER
{
    int x;
    int y;
    int Dest_x;
    int Dest_y;
};
 
/* 조건에 맞는 손님을 찾기 위한 정보를 관리하는 구조체 */
/* 알아야할 정보 = [ x좌표 , y좌표 , 거리 , 손님의 번호 ] */
struct INFO
{
    int x;
    int y;
    int Dist;
    int Num;
};
 
int N, M, Fuel;
int Taxi_x, Taxi_y;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
CUSTOMER Customer[MAX * MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input() {
    cin >> N >> M >> Fuel;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1) MAP[i][j] = -1;
            // 맵에서 벽으로 표시되는 1을 -1로 변경.
        }
    }
    cin >> Taxi_x >> Taxi_y;
    Taxi_x--; Taxi_y--;
    for (int i = 1; i <= M; i++)
    {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        Customer[i] = { a, b, c, d };
        MAP[a][b] = i;
        // 손님이 있는 위치를 각 손님의 번호로 변경
    }
}
 
bool Info_Cmp(INFO A, INFO B) {
    /* 조건에 맞는 손님을 찾기 위해서 Vector를 정렬하기 위한 기준 설정. */
    if (A.Dist <= B.Dist)
    {
        if (A.Dist == B.Dist)
        {
            if (A.x <= B.x)
            {
                if (A.x == B.x)
                {
                    if (A.y < B.y)
                    {
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
bool BFS(int a, int b, int c, int d, int Num) {
    /* 손님을 최단 거리로 목적지까지 이동시키기 위한 BFS 탐색 함수. */
    memset(Visit, false, sizeof(Visit));
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(a, b), make_pair(0, Fuel)));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Distance = Q.front().second.first;
        int Spare_Fuel = Q.front().second.second;
        Q.pop();
 
        /* 목적지에 도달한다면 ? */
        /* 연료의 양을 문제의 조건에 맞게 재설정. */
        /* 택시의 위치를, 현재 이동시킨 손님의 목적지 위치로 재설정. */
        if (Spare_Fuel < 0) return false;
        if (x == c && y == d)
        {
            Fuel = Fuel - Distance;
            Fuel = Fuel + (Distance * 2);
            Taxi_x = x;
            Taxi_y = y;
            return true;
        }
        /* 더 이상 연료가 없다면 ? = 손님을 더 이상 이동시킬 수 없다. */
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] != -1 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(Distance + 1, Spare_Fuel - 1)));
                }
            }
        }
    }
    return false;
}
 
int Find_Shortest_Customer() {
    /* 현재 택시 위치에서 가장 가까운 손님을 찾기 위한 BFS함수. */
    memset(Visit, false, sizeof(Visit));
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(Taxi_x, Taxi_y), make_pair(0, Fuel)));
    Visit[Taxi_x][Taxi_y] = true;
    vector<INFO> V;
    /* 위의 벡터가 "현재 연료의 양으로 찾아갈 수 있는 모든 손님에 대한 정보"를 저장. */
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Distance = Q.front().second.first;
        int Spare_Fuel = Q.front().second.second;
        Q.pop();
 
        /* 맵이 1 이상이라는 것은 해당 좌표에 손님이 있음을 의미. */
        /* 따라서, 해당 좌표에 있는 손님에 대한 정보를 Vector에 저장. */
        if (Spare_Fuel < 0) continue;
        if (MAP[x][y] >= 1) V.push_back({ x, y, Distance, MAP[x][y] });
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] != -1 && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(Distance + 1, Spare_Fuel - 1)));
                }
            }
        }
    }
 
    /* Vector의 Size = 0 이라는 것은 찾아갈 수 있는 손님이 없음을 의미. */
    if (V.size() == 0) return -1;
 
    /* 그게 아니라면, 우리가 찾는 딱 한명의 손님을 찾기 위해서 Vector를 정렬. */
    /* 해당 손님은 이제 더 이상 해당 좌표에 없으므로 맵에서 값 변경. */
    /* 현재 택시 위치에서 해당 손님까지 가는데 든 연료만큼 연료의 양 또한 변경. */
    sort(V.begin(), V.end(), Info_Cmp);
    MAP[V[0].x][V[0].y] = 0;
    Fuel = Fuel - V[0].Dist;
    return V[0].Num;
}
 
void Solution() {
    /* 아무리 많아도 손님의 수 만큼만 움직이면 된다. */
    /* 따라서, 0 ~ M번까지만 반복. */
    for (int i = 0; i < M; i++)
    {
        int Num = Find_Shortest_Customer();
        if (Num == -1)
        {
            cout << -1 << endl;
            return;
        }
 
        bool Move = BFS(Customer[Num].x, Customer[Num].y, Customer[Num].Dest_x, Customer[Num].Dest_y, Num);
        if (Move == false)
        {
            cout << -1 << endl;
            return;
        }
    }
    cout << Fuel << endl;
}
 
void Solve() {
    Input();
    Solution();
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}