[BOJ] 백준 19238 스타트 택시

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

6 3 15

0 0 1 0 0 0

0 0 1 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 1 0

0 0 0 1 0 0

6 5

2 2 5 6

5 4 1 6

4 2 3 5

　 

 Output 

14　

BFS와 시뮬레이션을 이용하는 문제입니다.

예외처리할 사항이 다소 많기 때문에 주의해야 합니다.

 

▶ 예외 Case를 제외하고 모든 승객을 태울 때까지 아래 작업 수행

① 현재 택시에서 가장 가까운 승객을 찾아 택시 이동

    - 승객 → 택시까지의 최단 거리 위치한 승객을 찾지 않고

      택시 → 승객으로 BFS 탐색해서 가장 가까운 승객을 찾습니다.

    * 동일한 거리인 사람이 많을 경우, 행/열이 작은 순으로 우선순위 결정

    * 현재 가지고 있는 연료로 이동가능한 거리여야 합니다.

    * 택시가 위치한 곳에 승객이 함께 위치할 수 있습니다. (필요 연료 = 0)

    * 승객을 태우고 이동한 거리만큼 연료가 소진됩니다.

    * 빈칸에 승객이 존재하며, 택시는 한 사람만 태울 수 있습니다.

      즉, 여러사람을 못 태울뿐 사람이 서있어도 택시는 거기를 지나갈 수 있다. 

② 승객을 태우고, 해당 승객의 목적지로 BFS 탐색으로 최단거리 이동합니다.

    * 각 승객의 출발지와 목적지는 다르지만, 해당 목적지가 다른 사람의 출발지 일 수 있습니다.

       택시 입장에서는 도착하자마자 다른 사람을 태우게 됩니다.

        ex) map[][]에 출발지와 도착지를 모두 표시하여 구현하는 경우 덮어씌우기 주의

    * 승객을 태운 후에도 목적지가 벽에 막혀있거나 연료가 부족한 경우 도착하지 못할 수 있습니다.

    * 연료 충전은 승객을 태우고 목적지까지 이동한 거리만큼 더해집니다.

      (문제 내용에서는 "이동거리만큼 소진되고, 2배만큼 충전"으로 표현)

---

#include <stdio.h>
enum {
    WALL = -1,
    EMPTY = 0,
    PASSENGER = 2,
};
const int INF = 2e9;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
const int MAX_N = 20 + 2;
const int MAX_M = MAX_N * MAX_N + 2;
struct Person {
    int sx, sy, ex, ey;
}person[MAX_M];
 
struct Taxi {
    int x, y, fuel;
}taxi;
 
struct Que {
    int x, y, dist;
}que[MAX_N * MAX_N * 4];
int fr, re;
int visited[MAX_N][MAX_N], map[MAX_N][MAX_N];
int N, M, passengerCnt;
void input() {
    // map 크기, 승객 수, 초기 연료
    scanf("%d %d %d", &N, &M, &taxi.fuel);
    passengerCnt = M;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf("%d", &map[i][j]);
            // 벽을 "1" 대신에 "-1"로 표현
            if (map[i][j] == 1) map[i][j] = WALL;
        }
    }
    scanf("%d %d", &taxi.x, &taxi.y);
    for (int i = 1; i <= M; ++i) {
        scanf("%d %d %d %d", &person[i].sx, &person[i].sy, &person[i].ex, &person[i].ey);
        // 승객이 위치한 곳(출발지) "i" 표시(1 ~ M)
        map[person[i].sx][person[i].sy] = i;
    }
}
 
void queInit() {
    fr = re = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            visited[i][j] = INF;
        }
    }
}
 
int comp(int A, int B) {
    // 행 번호가 같은 경우
    if (person[A].sx == person[B].sx) {
        // B의 열 번호가 작으면 결과 = True
        return person[A].sy > person[B].sy;
    }
    // B의 행 번호가 작으면 결과 = True
    return person[A].sx > person[B].sx;
}
 
int carryPerson() {
    queInit();
    que[re++] = { taxi.x, taxi.y, 0 };
 
    int dist = INF;
    int ID = EMPTY;
 
    while (fr < re) {
        Que cur = que[fr++];
        // 승객이 존재하는 경우
        if (map[cur.x][cur.y] > 0) {
            // 처음 승객을 발견한 경우거나 더 가까운 거리의 승객인 경우
            if (dist == INF || cur.dist < dist) {
                dist = cur.dist; // 이동 거리(= 필요 연료)
                ID = map[cur.x][cur.y]; // 대상 승객
            }
            // 이미 승객을 찾은 경우, 우선순위가 높은지 확인
            else if (dist != INF && cur.dist == dist) {
                if (comp(ID, map[cur.x][cur.y]))
                    ID = map[cur.x][cur.y];
            }
            continue;
        }
 
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            // 격자를 벗어나는 경우
            if (nextX < 1 || nextY < 1 || nextX > N || nextY > N) continue;
            // 벽(-1)인 경우
            if (map[nextX][nextY] == WALL) continue;
 
            // 같거나 보다 빠르게 방문한 경우
            if (visited[nextX][nextY] <= cur.dist + 1) continue;
 
            // 가진 연료보다 거리가 먼 경우
            if (cur.dist + 1 > taxi.fuel) continue;
 
            visited[nextX][nextY] = cur.dist + 1;
            que[re++] = { nextX, nextY, cur.dist + 1 };
        }
    }
    if (ID != EMPTY) {
        taxi.x = person[ID].sx;
        taxi.y = person[ID].sy;
        taxi.fuel -= dist;
        map[taxi.x][taxi.y] = EMPTY;
    }
    return ID;
}
 
bool getEndDistance(int ID) {
    queInit();
    que[re++] = { taxi.x, taxi.y, 0 };
    
    while (fr < re) {
        Que cur = que[fr++];
        // 해당 승객의 목적지로 도착한 경우
        if (cur.x == person[ID].ex && cur.y == person[ID].ey) {
            taxi.x = person[ID].ex;
            taxi.y = person[ID].ey;
            // 연료 충전
            taxi.fuel += cur.dist;
            return true;
        }
 
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            // 격자를 벗어나는 경우
            if (nextX < 1 || nextY < 1 || nextX > N || nextY > N) continue;
            // 벽(-1)인 경우
            if (map[nextX][nextY] == WALL) continue;
 
            // 같거나 보다 빠르게 방문한 경우
            if (visited[nextX][nextY] <= cur.dist + 1) continue;
 
            // 가진 연료보다 거리가 먼 경우
            if (cur.dist + 1 > taxi.fuel) continue;
 
            visited[nextX][nextY] = cur.dist + 1;
            que[re++] = { nextX, nextY, cur.dist + 1 };
        }
    }
    return false;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
 
    // 모든 승객을 태울 때까지
    while (passengerCnt > 0) {
        // 현재 택시에서 가장 가까운 승객을 찾아 택시 이동
        int ID = carryPerson();
        if (ID == EMPTY) {
            printf("-1\n");
            return 0;
        }
 
        // 승객을 태운 시점에서 목적지까지의 최단거리로 이동
        if (!getEndDistance(ID)) {
            printf("-1\n");
            return 0;
        }
 
        passengerCnt--;
    }
    printf("%d\n", taxi.fuel);
    return 0;
}