ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 19238.스타트 택시
    알고리즘/백준 BAEK JOON 2020. 8. 30. 18:20

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

     

    19238번: 스타트 택시

    첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다

    www.acmicpc.net

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

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

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

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

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

     


     

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

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

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

     

     

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

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

     

     


     

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

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

     

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

     

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

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

     

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

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

    택시 -> 승객 1회

    승객 -> 목적지 1회

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

     

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

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

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

     

     

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

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

     

     

     


     

    < Code 설명 >

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243

    #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= { 001-1 };
    int dy[4= { 1-100 };
    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<intint>>taxi; // 택시의 위치 좌표
     
     
    deque<man>tmp;               // 승객 정보
    deque<pair<intint>> start; // 승객 출발지(출발지에서 목적지까지의 연료량을 구할때만 사용)
    deque<pair<intint>> 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, 0sizeof(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;
    }
    cs

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    19237.어른상어  (0) 2020.09.17
    19236.청소년상어  (0) 2020.09.09
    19238.스타트 택시  (0) 2020.08.30
    1197.최소 스패닝 트리  (0) 2020.08.20
    9372.상근이의 여행  (0) 2020.08.20
    1932.정수 삼각형  (0) 2020.08.19

    댓글 0

Designed by Tistory.