[BOJ/백준] 19238 스마트 택시 (G2)

문제

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

풀이

위 문제의 핵심을 나열해 보며 아래와 같다.

1. 택시의 현재 위치 기준 가장 가까운 고객을 태워서 목적지에 데려다 준다.
2. 만약, 거리가 가까운 고객이 여러 명일 경우 행과 열이 작은 고객을 먼저 태운다.
3. 고객을 태우기 전 택시의 위치에서 고객의 위치까지 이동하는 동안 소비된 연료를 총 연료에서 차감한다. 그리고 목적지에 도착하면 손님이 탑승한 위치에서 목적지 까지의 연료를 차감한 후, 고객의 위치부터 목적지까지 이동하면서 소비한 연료의 양의 2배를 채운다.
4. 단, 연료가 떨어지면(0이 되면) 즉시 운행을 종료한다.
5. 모든 고객을 목적지에 데려갔을 때, 남아있는 연료의 양을 결과로 출력한다.
6. 모든 고객을 목적지에 데려가지 못할 경우, -1을 결과로 출력한다.

풀이를 대략적으로 나열해보면 우선 값들을 입력받고, 승객을 찾아가서  승객을 목적지에 데려다주고 택시의 현재 위치를 최신화하며 반복하는 과정을 거치면서 연료의 양을 최신화하며 진행한다.

 

1. 입력

모든 값들은 일반적으로 받았지만 손님의 출발지와 도착지에 대한 좌표는 Node라는 클래스를 정의하여 입력을 받았다. 위 핵심 조건에서 2번을 보면 각 조건에 동일한 손님들이 여러 명인 경우에는 행과 열이 작은 고객을 먼저 태워야 하기 때문에 Node 내에 Comparable의 compareTo를 @Override해서 적용했다.

class Node implements Comparable<Node> {
    int row, col, dist;  // row, col, 거리

    @Override
    public int compareTo(Node o) {
        if (this.dist == o.dist) {
            if (this.row == o.row) {
                return this.col - o.col;  // 거리와 row가 같은면 col 오름차순
            }
            return this.row - o.row;  // 거리가 같으면 row 오름차순
        }
        return this.dist - o.dist;  // 거리 오름차순
    }

    /** 생성자들 */
}

추가적으로 map을 입력받는 과정에서 벽을 입력받으면 해당 칸에 Integer.MAX_VALUE가 저장되도록 했는데 이는 고객의 위치를 지도에 저장할 때, 고객 번호가 벽의 값인 1과 겹치기 때문에 벽의 값을 최댓값으로 지정했다.

2. 승객을 찾아가는 부분

고객들의 인원수를 차감하면서 while문을 진행한다. findPassenger()라는 메서드를 통해 2번 조건에 만족하는 태워야 하는 고객 번호를 져오는 부분이다.

findPassenger() 메서드에서는 Queue를 사용하여 BFS를 진행하며 택시는 상하좌우로 한 칸씩만 이동이 가능하다. 또한 이 과정을 반복하면서 승객을 만나거나, 벽을 만나거나, 연료가 바닥난 경우에는 각 조건에 맞춰 종료하게 된다.

다음에 이동할 칸의 좌표가 지도 범위 안에 있고, 해당 칸의 값이 최댓값(Integer.MAX_VALUE)이면 안되고, 방문하지 않은 칸이라면 해당 칸을 방문처리 하고, 해당 칸을 Queue에 넣어서 이동한다.

/** 택시가 승객의 위치를 찾는 메서드 */
private static int findPassenger(int startRow, int startCol) {  // 택시의 현재 위치에서 승객을 찾아 bfs
    boolean [][] visited = new boolean[N + 1][N + 1];
    Queue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(startRow, startCol, 0));  // 출발 위치
    visited[startRow][startCol] = true;  // 출발지 방문 처리

    while (!queue.isEmpty()) {
        Node now = queue.poll();
        // 현재 위치가 0이 아닌 경우 (승객을 만나거나, 벽이 있는 경우) -> return
        if (map[now.row][now.col] != 0) {
            fuel -= now.dist;
            if (fuel < 0) {
                canGo = false;
            }
            int consumerNum = map[now.row][now.col];  // 승객을 만난 경우라면, 승객 번호(map[now.row][now.col])를 저장
            map[now.row][now.col] = 0;  // 승객이 있던 위치를 빈칸 처리

            return consumerNum;
        }
        for (int i = 0; i < 4; i++) {
            int nextR = now.row + dr[i];
            int nextC = now.col + dc[i];

            // 다음 방문할 좌표가 map 안에 위치해야 하고, map[nextR][nextC]에 해당하는 값이 정수 최대값이면 안되고, 방문하지 않은 지점이라면?
            if (nextR >= 1 && nextC >= 1 && nextR <= N && nextC <= N && map[nextR][nextC] != Integer.MAX_VALUE && !visited[nextR][nextC]) {
                visited[nextR][nextC] = true;  // 방문처리하고,
                queue.add(new Node(nextR, nextC, now.dist + 1));  // queue에 추가
            }
        }
    }

    return 0;
}

만약 위 과정을 진행했을 때, 연료가 바닥나면 canGo 값을 false로 지정하고 이후에 다시 main을 진행할 때, 연료의 상태가 0이거나 고객을 찾지 못한 경우(0)에 진행되는 if문에 걸려서 -1을 출력하고 종료하게 된다.

3. 승객을 태우고 승객을 목적지로 데려가주는 부분

이 부분 또한 BFS로 진행하며 승객을 태우는 부분의 메서드와 동일하지만 목적지에 도착했을 때의 처리 부분이 추가되었다.

목적지에 도착하면, 일단 승객을 태우고 목적지로 이동한 만큼의 연료의 양을 감소시키는데, 만약, 연료가 없다면 canGo 값을 false로 설정하여 main으로 돌아갔을 때, 운행이 종료됨을 알린다.

그리고 소비한 연료의 양을 2배 만큼 증가시키고 반환한다.

/** 택시가 승객을 태우고 목적지까지 이동하는 메서드 */
private static void goToArrival(int startRow, int startCol, int arrivalRow, int arrivalCol) {  // 택시가 승객의 위치에서 목적지를 찾기위한 bfs

    /** findPassenger() 승객을 찾는 메서드와 동일 */

    while (!queue.isEmpty()) {
        Node now = queue.poll();

        // 목적지에 도착하면?
        if (now.row == arrivalRow && now.col == arrivalCol) {
            fuel -= now.dist; // 일단 연료 감소
            if (fuel < 0) {  // fuel이 0이면 다음 승객을 태울 수 없음 -> 종료
                canGo = false;
            }
            fuel += now.dist * 2;  // 승객이 도착지에 내렸으므로 승객이 탑승한 위치부터 도착지까지의 연료 소비량(now.dist) * 2 만큼 충전
            return;
        }

            /** findPassenger() 승객을 찾는 메서드와 동일 */
    }
    canGo = false;  // 목적지에 도착하지 못함
}

4. 출력

while문을 탈출하면 연료의 양을 출력한다.

Code

import java.io.*;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M, fuel;  // N*N: 판, M: 승객 수, fuel: 연료
    static int [][] map;  // 지도
    static boolean canGo = true;
    static Node [] start;  // 출발지 좌표
    static Node [] arrival;  // 도착지 좌표

    static int [] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        fuel = Integer.parseInt(st.nextToken());

        map = new int[N + 1][N + 1];
        start = new Node[M + 1];  // 출발지와 도착지의 각 개수는 손님 수와 동일
        arrival = new Node[M + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    map[i][j] = Integer.MAX_VALUE;  // 밑에서 승객 번호를 입력받을 때, 승객 번호와 벽이 1로 겹치므로 벽을 최대 정수 값으로 표현
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int startTaxiRow = Integer.parseInt(st.nextToken());
        int startTaxiCol = Integer.parseInt(st.nextToken());

        // 승객 별 출발지와 도착지 좌표
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int startRow = Integer.parseInt(st.nextToken());
            int startCol = Integer.parseInt(st.nextToken());
            int arrivalRow = Integer.parseInt(st.nextToken());
            int arrivalCol = Integer.parseInt(st.nextToken());

            map[startRow][startCol] = i;  // 승객의 출발지 좌표에 승객 번호를 저장
            start[i] = new Node(startRow, startCol);  // 승객의 출발지 좌표를 저장
            arrival[i] = new Node(arrivalRow, arrivalCol);  // 승객의 도착지 좌표를 저장
        }

        while (M-- > 0) {
            // 각 승객을 찾아가는 부분
            int passenger = findPassenger(startTaxiRow, startTaxiCol);  // bfs

            if (!canGo || passenger == 0) {  // 도착지로 갈 수 없거나 승객이 없을 때,
                bw.write("-1");;
                bw.close();bw.close();
                return;
            }

            // 승객의 위치에서 목적지로 이동
            goToArrival(start[passenger].row, start[passenger].col, arrival[passenger].row, arrival[passenger].col);

            // 택시가 승객의 목적지에 도착하면, 택시의 위치를 저장(최신화)
            startTaxiRow = arrival[passenger].row;
            startTaxiCol = arrival[passenger].col;

            if (!canGo) {
                bw.write("-1");;
                bw.close();bw.close();
                return;
            }
        }
        bw.write(fuel + "");
        bw.close();bw.close();
    }

    /** 택시가 승객의 위치를 찾는 메서드 */
    private static int findPassenger(int startRow, int startCol) {  // 택시의 현재 위치에서 승객을 찾아 bfs
        boolean [][] visited = new boolean[N + 1][N + 1];
        Queue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(startRow, startCol, 0));  // 출발 위치
        visited[startRow][startCol] = true;  // 출발지 방문 처리

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            // 현재 위치가 0이 아닌 경우 (승객을 만나거나, 벽이 있는 경우) -> return
            if (map[now.row][now.col] != 0) {
                fuel -= now.dist;
                if (fuel < 0) {
                    canGo = false;
                }
                int consumerNum = map[now.row][now.col];  // 승객을 만난 경우라면, 승객 번호(map[now.row][now.col])를 저장
                map[now.row][now.col] = 0;  // 승객이 있던 위치를 빈칸 처리

                return consumerNum;
            }
            for (int i = 0; i < 4; i++) {
                int nextR = now.row + dr[i];
                int nextC = now.col + dc[i];

                // 다음 방문할 좌표가 map 안에 위치해야 하고, map[nextR][nextC]에 해당하는 값이 정수 최대값이면 안되고, 방문하지 않은 지점이라면?
                if (nextR >= 1 && nextC >= 1 && nextR <= N && nextC <= N && map[nextR][nextC] != Integer.MAX_VALUE && !visited[nextR][nextC]) {
                    visited[nextR][nextC] = true;  // 방문처리하고,
                    queue.add(new Node(nextR, nextC, now.dist + 1));  // queue에 추가
                }
            }
        }

        return 0;
    }

    /** 택시가 승객을 태우고 목적지까지 이동하는 메서드 */
    private static void goToArrival(int startRow, int startCol, int arrivalRow, int arrivalCol) {  // 택시가 승객의 위치에서 목적지를 찾기위한 bfs
        boolean [][] visited = new boolean[N + 1][N + 1];
        Queue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(startRow, startCol, 0));  // 출발 위치
        visited[startRow][startCol] = true;  // 출발지 방문 처리

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            // 목적지에 도착하면?
            if (now.row == arrivalRow && now.col == arrivalCol) {
                fuel -= now.dist; // 일단 연료 감소
                if (fuel < 0) {  // fuel이 0이면 다음 승객을 태울 수 없음 -> 종료
                    canGo = false;
                }
                fuel += now.dist * 2;  // 승객이 도착지에 내렸으므로 승객이 탑승한 위치부터 도착지까지의 연료 소비량(now.dist) * 2 만큼 충전
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nextR = now.row + dr[i];
                int nextC = now.col + dc[i];

                // 다음 방문할 좌표가 map 안에 위치해야 하고, map[nextR][nextC]에 해당하는 값이 정수 최대값이면 안되고, 방문하지 않은 지점이라면?
                if (nextR >= 1 && nextC >= 1 && nextR <= N && nextC <= N && map[nextR][nextC] != Integer.MAX_VALUE && !visited[nextR][nextC]) {
                    visited[nextR][nextC] = true;  // 방문처리하고,
                    queue.add(new Node(nextR, nextC, now.dist + 1));  // queue에 추가
                }
            }
        }
        canGo = false;  // 목적지에 도착하지 못함
    }
}
class Node implements Comparable<Node> {
    int row, col, dist;  // row, col, 거리

    @Override
    public int compareTo(Node o) {
        if (this.dist == o.dist) {
            if (this.row == o.row) {
                return this.col - o.col;  // 거리와 row가 같은면 col 오름차순
            }
            return this.row - o.row;  // 거리가 같으면 row 오름차순
        }
        return this.dist - o.dist;  // 거리 오름차순
    }

    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public Node(int row, int col, int dist) {
        this.row = row;
        this.col = col;
        this.dist = dist;
    }
}