[백준] 19238번: 스타트 택시

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

문제 이해

1. 현재 택시의 위치에서 제일 가까운 손님 찾기 (BFS)

2. 손님을 태우고 도착지까지 최적 경로 찾기 (BFS)

 

BFS를 하는 것은 명백한데, 구체적으로 하는게 좀 복잡하다.

 

Find_Nearest_Customer()

모든 손님들에 대한 거리를 구해서 cus 배열에 넣어준다.

큐에 넣을 때는 남은 가스량과 거리를 함께 저장한다.

만약 가스가 동나면 그 손님한테까지는 못가는 것이다.

 

BFS를 완료하면 cus에는 현재 택시 위치에서 닿을 수 있는 손님들이 들어있다.

그럼 그 cus 배열을 거리, 행, 열로 정렬한 후에 맨 앞에 있는 손님을 선택한다. 

int Find_Nearest_Customer(void) {
    // 현재 위치에서 BFS를 하면서, 만약 손님의 위치라면 vector에 넣는다
    memset(visited, 0, sizeof(visited));
    memset(cus, 0, sizeof(cus));
    ccnt = 0;
    wp = rp = 0;
    
    enq(cury, curx, 0, G);
    visited[cury][curx] = 1;
    while (!empty()) {
        ELE cur = deq();
        if (map[cur.y][cur.x] > 0) { // 손님있는 위치
            cus[ccnt].y = cur.y, cus[ccnt].x = cur.x;
            cus[ccnt].dis = cur.dis, cus[ccnt++].gas = cur.gas;
        }
        if (cur.gas == 0) continue; // 더이상 갈 수 없음
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (ny < 1 || ny > N || nx < 1 || nx > N) continue;
            if (map[ny][nx] == -1) continue; // 벽임
            if (visited[ny][nx] == 1) continue;
            visited[ny][nx] = 1;
            enq(ny, nx, cur.dis + 1, cur.gas-1);
        }
    }

    // cus에는 갈 수 있는 손님의 위치가 있다. 
    if (ccnt == 0) return 0; // 갈 데가 없음
    qsort(cus, ccnt, sizeof(cus[0]), comp);
    cury = cus[0].y, curx = cus[0].x;
    G -= cus[0].dis;
    int idx = map[cury][curx];
    map[cury][curx] = 0;
    return idx;
}

 

Drive_To_Destination()

선택한 손님의 출발지에서 손님의 도착지까지 가는 최단 경로를 구한다. 

이때, 가스가 동났는지를 확인해야 하는데, 가스가 0이 되었다고 바로 return을 하면 안된다.

왜냐면 아직 큐에 경로들이 남아있기 떄문이다. 가스가 0인데 도착지에 도착한 거면 okay이기 때문이다. 만약 큐에 가스0인데 도착한 경로가 있으면 그것들도 살펴봐야하므로 그냥 continue를 해준다. 

int Drive_To_Destination(int idx) {
    memset(visited, 0, sizeof(visited));
    wp = rp = 0;

    enq(cury, curx, 0, G);
    visited[cury][curx] = 1;
    while (!empty()) {
        ELE cur = deq();
        if (cur.y == C[idx].ey && cur.x == C[idx].ex) {
            // 도착함
            G -= cur.dis;
            G += cur.dis * 2;
            cury = cur.y, curx = cur.x;
            return 1;
        }
        if (cur.gas == 0) continue; // 더이상 갈 수 없음 -> 여기서 리턴하면 문제 생김!
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (ny < 1 || ny > N || nx < 1 || nx > N) continue;
            if (map[ny][nx] == -1) continue; // 벽임
            if (visited[ny][nx] == 1) continue;
            visited[ny][nx] = 1;
            enq(ny, nx, cur.dis + 1, cur.gas - 1);
        }
    }
    return 0;
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXN 20
#define MAXM 400
int N, M, G; // 맵 크기, 사람 수, 연료
int cury, curx; // 택시 위치
int map[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5];
typedef struct cust {
    int sy, sx, ey, ex;
}cust;
cust C[MAXM + 5];

void Get_Input(void) {
    scanf("%d %d %d", &N, &M, &G);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1) map[i][j] = -1; // 벽
        }
    }
    scanf("%d %d", &cury, &curx);
    for (int i = 1; i <= M; i++) {
        scanf("%d %d %d %d", &C[i].sy, &C[i].sx, &C[i].ey, &C[i].ex);
        map[C[i].sy][C[i].sx] = i;
    }
}

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

typedef struct {
    int y, x, dis, gas;
}ELE;
ELE q[MAXN * MAXN * 10];
ELE cus[MAXM + 10];
int ccnt; 
int wp, rp;
void enq(int y, int x, int dis, int gas) {
    q[wp].y = y, q[wp].x = x, q[wp].dis = dis, q[wp++].gas = gas;
}
ELE deq(void) { return q[rp++]; }
int empty(void) { return rp == wp; }

int comp(const void* a, const void* b) {
    ELE* p = (ELE*)a;
    ELE* q = (ELE*)b;
    if (p->dis == q->dis) {
        if (p->y == q->y) {
            return p->x - q->x;
        }
        else return p->y - q->y;
    }
    else return p->dis - q->dis;
}

int Find_Nearest_Customer(void) {
    // 현재 위치에서 BFS를 하면서, 만약 손님의 위치라면 vector에 넣는다
    memset(visited, 0, sizeof(visited));
    memset(cus, 0, sizeof(cus));
    ccnt = 0;
    wp = rp = 0;
    
    enq(cury, curx, 0, G);
    visited[cury][curx] = 1;
    while (!empty()) {
        ELE cur = deq();
        if (map[cur.y][cur.x] > 0) { // 손님있는 위치
            cus[ccnt].y = cur.y, cus[ccnt].x = cur.x;
            cus[ccnt].dis = cur.dis, cus[ccnt++].gas = cur.gas;
        }
        if (cur.gas == 0) continue; // 더이상 갈 수 없음
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (ny < 1 || ny > N || nx < 1 || nx > N) continue;
            if (map[ny][nx] == -1) continue; // 벽임
            if (visited[ny][nx] == 1) continue;
            visited[ny][nx] = 1;
            enq(ny, nx, cur.dis + 1, cur.gas-1);
        }
    }

    // cus에는 갈 수 있는 손님의 위치가 있다. 
    if (ccnt == 0) return 0; // 갈 데가 없음
    qsort(cus, ccnt, sizeof(cus[0]), comp);
    cury = cus[0].y, curx = cus[0].x;
    G -= cus[0].dis;
    int idx = map[cury][curx];
    map[cury][curx] = 0;
    return idx;
}

int Drive_To_Destination(int idx) {
    memset(visited, 0, sizeof(visited));
    wp = rp = 0;

    enq(cury, curx, 0, G);
    visited[cury][curx] = 1;
    while (!empty()) {
        ELE cur = deq();
        if (cur.y == C[idx].ey && cur.x == C[idx].ex) {
            // 도착함
            G -= cur.dis;
            G += cur.dis * 2;
            cury = cur.y, curx = cur.x;
            return 1;
        }
        if (cur.gas == 0) continue; // 더이상 갈 수 없음 -> 여기서 리턴하면 문제 생김!
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (ny < 1 || ny > N || nx < 1 || nx > N) continue;
            if (map[ny][nx] == -1) continue; // 벽임
            if (visited[ny][nx] == 1) continue;
            visited[ny][nx] = 1;
            enq(ny, nx, cur.dis + 1, cur.gas - 1);
        }
    }
    return 0;
}

int main(void) {
    int flag = 1;
    freopen("in.txt", "r", stdin);
    Get_Input();
    for(int i = 0; i<M; i++) {
        // 1. 현재 위치에서 가장 가까운 승객을 찾는다
        int idx = Find_Nearest_Customer(); // 거기까지 거리 반환
        if (idx == 0) {
            flag = 0;
            break;
        }
        // 2. 승객을 거기까지 태운다. 
        if (!Drive_To_Destination(idx)) {
            flag = 0;
            break; // 만약 실패 시 끝
        }
    }
    if (flag == 0) printf("-1");
    else printf("%d", G);
    return 0;
}