19238.스타트 택시

이번에 풀어볼 문제는 백준의 19238번 스타트 택시이다.

19238번: 스타트 택시

제일 최근에 나온 문제로 역시나 시뮬레이션이다. 

난이도는 19%라고 나와있지만 함정만 잘피하면 풀 수 있다.

이 문제를 다 구현하고 시간을 어느정도 잡아먹었는데.. 그 이유는.. 문제의 조건 하나를 읽어놓고

구현하다가 까먹었다. ( "최단 거리가 같은 경우 가로, 세로 좌표가 작은게 우선이다" 라는 조건이다.. )

항상 조건들은 잘 적어 놓고 빼먹지 말자!!!

 

---

 

함정은 크게 2가지 정도가 있다.

1. 승객을 태우러 가거나 태우고나서 목적지에 갈 수 없는 경우

-> 벽으로 인해서 못가는 경우다 예제 3번이 그렇다.

 

 

2. 승객을 태우고나서 목적지에 내려주고보니 그 목적지가 다른승객의 출발지인 경우

-> 이 경우도 많이들 빼먹는거 같다.

 

 

---

 

나의 로직의 순서는 다음과 같다.

1. 우선 입력을 다 받는다.

 

2. 승객을 태우고 나서 그 승객이 목적지에 도착까지 필요한 연료랑을 미리 구해놓는다.

 

3. 어떤 승객을 먼저 태울 것인지를 구한다.

=> 택시에서 승객까지의 연료량을 각각 구한다(연료량이 곧 거리이므로 자연스럽게 구해진다)

 

4. 운행을 시작한다. 우선순위로 선택한 승객을 태우고 필요한 연료를 사용한다.

만약 승객과의 거리가 같은 승객이 여러명 있다면 우선순위를 구별하는 로직을 넣어준다.

택시 -> 승객 1회

승객 -> 목적지 1회

총 2회의 연료사용이 진행되고 이 때 가진 연료보다 부족해진다면 -1을 출력하도록 flag변수를 지정한다.

 

5. 택시의 좌표를 승객의 목적지 좌표로 옮겨주고 3번부터 다시 진행하도록 한다.

-> 이 반복은 어처피 승객 수만큼만 진행하면된다.

-> 나의 경우, 내려준 승객의 필요 연료량을 -1로 함으로써 3번에서 다시 우선순위 승객을 찾을때 pass시켰다.

 

 

각자의 로직이 있겠지만 나는 중복되는 로직을 함수로 굳이 나누지 않았다.

=> 그 이유는 실수할까봐 쫄았다;; 앞으로는 좀 더 설계를 세심히해서 중복도 함수로 진행해봐야겠다.

 

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <deque>
#include <string.h>
 
#define MAX 21
 
using namespace std;
 
int N, M, gas;       // map크기, 승객 수, 남은 연료
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int map[MAX][MAX];   // map
int check[MAX][MAX]; // 이동 거리를 위한 배열
bool cant_go = false;
  
struct man{
    int a, b, c, d; //( 출발좌표:a,b),(목적지좌표:c,d)
    int gas1; //택시에서 출발지까지 필요한 연료량
    int gas2; //출발지부터 목적지까지 필요한 연료량
};
 
deque<man>info; // 승객 정보
deque<pair<int, int>>taxi; // 택시의 위치 좌표
 
 
deque<man>tmp;               // 승객 정보
deque<pair<int, int>> start; // 승객 출발지(출발지에서 목적지까지의 연료량을 구할때만 사용)
deque<pair<int, int>> mov;   // 이동하는 택시 좌표
 
void info_check() { // 디버깅용
    for (int i = 0; i < M; i++){
        printf("%d %d %d %d %d %d \n", info[i].a, info[i].b, info[i].c, info[i].d, info[i].gas1, info[i].gas2);
    }
}
 
void init(int a){// 초기화 함수
    if (a == 0){ //gas init();
        start.clear();
        tmp.pop_back();
    }
    else if (a == 1){ // taxi init();
        taxi.clear();
    }
    else if (a == 2){ // mov init();
        mov.clear();
    }
    memset(check, 0, sizeof(check));
}
 
void search(int idx){ // 시작 택시부터 승객까지 이동거리(연료량) 구하는 함수
    int x, y;
    bool flag = true; 
    check[taxi.front().first][taxi.front().second] = 1;
 
    int d_x = info[idx].a; //도착좌표
    int d_y = info[idx].b; //도착좌표
 
    while (flag){
        if (taxi.empty()){ //벽에 막혀서 갈 수 없는 경우
            cant_go = true;
            break;
        }
        x = taxi.front().first;
        y = taxi.front().second;
        taxi.pop_front();
 
        for (int i = 0; i < 4; i++){
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax <= 0 || ay <= 0 || ax > N || ay > N)
                continue;
            if (!check[ax][ay] && map[ax][ay] == 0){
                check[ax][ay] = check[x][y] + 1;
                taxi.push_back(make_pair(ax, ay));
            }
            if (ax == d_x && ay == d_y){
                info[idx].gas1 = check[ax][ay]-1; // 택시로 부터 새당 승객의 거리(필요연료량) 저장
                flag = false;                     // 구했으므로 종료플래그 on
                break;
            }
        }
    }
}
 
void move(int idx){ // 택시부터 승객까지 이동거리(연료량) 구하는 함수
    int x, y;
    bool flag = true;
    check[mov.front().first][mov.front().second] = 1;
 
    int d_x = info[idx].a; //도착좌표
    int d_y = info[idx].b; //도착좌표
 
    while (flag){ //벽에 막혀서 갈 수 없는 경우
        if (mov.empty()){ 
            cant_go = true;
            break;
        }
        x = mov.front().first;
        y = mov.front().second;
        mov.pop_front();
 
        for (int i = 0; i < 4; i++){
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax <= 0 || ay <= 0 || ax > N || ay > N)
                continue;
            if (!check[ax][ay] && map[ax][ay] == 0){
                check[ax][ay] = check[x][y] + 1;
                mov.push_back(make_pair(ax, ay));
            }
            if (ax == d_x && ay == d_y){
                info[idx].gas1 = check[ax][ay] - 1;
                flag = false;
                break;
            }
        }
    }
 
}
void gas_check(int idx){ // 승객부터 목적지까지 이동거리(연료량) 구하는 함수
    int x, y, gas;
    bool flag = true;
    start.push_back(make_pair(tmp.front().a, tmp.front().b));
    check[start.front().first][start.front().second] = 1;
 
    int d_x = tmp.front().c; //도착좌표
    int d_y = tmp.front().d; //도착좌표
 
    while (flag){
        if (start.empty()){ // 도달하지 못하는 경우
            cant_go = true;
            break;
        }
        x = start.front().first;
        y = start.front().second;
        start.pop_front();
 
        for (int i = 0; i < 4; i++){
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax <= 0 || ay <= 0 || ax > N || ay > N)
                continue;
            if (!check[ax][ay] && map[ax][ay] == 0){
                check[ax][ay] = check[x][y] + 1;
                start.push_back(make_pair(ax, ay));
            }
            if (ax == d_x && ay == d_y){
                info[idx].gas2 = check[ax][ay]-1;
                flag = false;
                break;
            }
        }
    }
}
 
int main() {
    freopen("19238.txt", "r", stdin);
    cin >> N >> M >> gas; // map의 길이와 승객 수, 연료량 저장
 
    for (int i = 1; i <= N; i++){     // map 저장
        for (int j = 1; j <= N; j++){
            cin >> map[i][j];
        }
    }
 
    int x, y; // taxi 시작 좌표 저장
    cin >> x >> y;
 
    int q, w, e, r; // 승객들의 출발지 좌표와 목적지 좌표 저장
 
    for (int i = 0; i < M; i++){ // 승객을 태우고 부터 목적지까지의 연료랑 구하기
        cin >> q >> w >> e >> r;
        tmp.push_back({ q, w, e, r });
        info.push_back({ q, w, e, r });
        gas_check(i);
        init(0);
    }
 
    for (int i = 0; i < M; i++){         // 승객 중 누굴 먼저 태울 것인지 && 그 승객까지의 필요 연료량 구하기
        taxi.push_back(make_pair(x, y)); //택시좌표 넣기
        search(i);
        init(1);
    }
 
    for (int t = 0; t < M; t++){ // 택시 운행 시작
        int g = 987654321; // 최단거리 비교 변수
        int start_idx = 0; // 이동 후 시작점이 될 택시 좌표
        int w_gas;         // 소모 가스 변수
 
        for (int i = 0; i < M; i++){     // 어떤 승객을 먼저 태울지 정함
            if (info[i].gas1 != -1 && g >= info[i].gas1){ //최단거리(최소 필요 연료량)일 경우 && gas1이 -1이면 이미 내린 승객이므로 pass
                if (g == info[i].gas1){ // 승객과의 거리가 같은 승객이 어려명일 경우
                    if (info[start_idx].a > info[i].a){ // 가로 좌표이 작은 승객 우선
                        start_idx = i;
                    }
                    else if (info[start_idx].a == info[i].a){ // 가로 좌표가 마저 같다면
                        if (info[start_idx].b > info[i].b)    // 세로 좌표가 작은 승객 우선
                            start_idx = i;
                    }
 
                }
                else{ // 승객과의 거리가 같은 경우가 없다면
                    g = info[i].gas1; // 택시로 부터 최단 거리 승객의 필요 연료량을 비교변수에 넣는다.
                    start_idx = i; // 해당 승객의 idx도 저장
                }
            }
 
        }
 
        w_gas = info[start_idx].gas1; //택시가 승객을 태우러 가기까지 소모 가스
 
        if (gas - w_gas >= 0){ // 가진 연료로 충분히 갈 수 있다면
            gas -= w_gas; // 연료 소모시킴
            w_gas = info[start_idx].gas2; // 태우고 나서 목적지까지의 소모 가스
            if (gas - w_gas >= 0){
                gas -= w_gas; // 연료소모시킴
                gas += w_gas * 2; // 태우고 이동거리x2 만큼의 가스 충전
                info[start_idx].gas1 = -1; // 해당 승객은 이제 안태울 것이므로 -1으로 초기화
                //cout << gas << endl;
                for (int i = 0; i < M; i++){         // 승객 중 누굴 먼저 태울 것인지 구하기
                    init(2);
                    mov.push_back(make_pair(info[start_idx].c, info[start_idx].d)); // 해당 승객을 태우고 목적지로 이동
                    if (info[i].gas1 == -1)           // 내린 승객은 건너뜀
                        continue;
                    move(i);                          // 택시에서 승객까지의 연료량 구함
                }
            }
            else if (gas - w_gas < 0){ // 연료가 바닥 났으므로 종료
                cant_go = true;
                break;
            }
        }
    }
 
    if (!cant_go)    // 못가는 flag가 false 일 경우
        cout << gas; // 남은 연료 출력
    else
        cout << "-1";// 못가는 flag가 true 일 경우
       
    return 0;
}