백준 19238번: 스타트 택시 (JAVA)

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

19238번: 스타트 택시

문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

<그림 1>

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>

<그림 3>

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>

<그림 5>

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

<그림 6>

<그림 7>

<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

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

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

 

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

 

---

 

풀이

M명의 손님에 대해 태우고, 목적지 데려다주고...를 M번 반복하여 남은 연료를 출력하면 된다. M명의 손님 모두를 목적지에 데려가지 못하는 경우에 대해서는 -1을 출력하면 된다. 문제를 이해하는 거 자체는 쉬운 편이고, 구현도 코드 길이가 좀 될뿐 bfs 2M번만 쓰면 된다.

다만, '손님 모두를 목적지로 데려가지 못하는 경우'의 케이스가 매우 많다. 손님을 태웠는데 손님의 목적지를 갈 수 없는 경우, 택시의 현재 위치에 손님이 바로 있는 경우 등... 자세한 건 링크를 참고하면 된다.(https://www.acmicpc.net/board/view/88714). 정답률 20%가 이를 방증한다.

그래서, 난이도 기여 항목을 보면 예외 중 하나에서 걸린 사람은 골드 2~1, 안 걸린 사람은 골드 5~4를 준 걸 볼 수 있다. 나는 예외 걸려서 틀렸으므로 골드 2 줬다. 근데 솔직히 코드 길이만 봐도 골드 5는 아닌거 같다. 예외 케이스 많은 '아기 상어' 같은데?

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int[] dr = {-1, 0, 0, 1};
    static int[] dc = {0, 1, -1, 0};
    static int N, M;
    static int[][] map, dest;
    static Taxi taxi;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        dest = new int[M+1][2]; // 목적지 row, col 저장
        int gas = Integer.parseInt(st.nextToken());
        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());
            }
        }

        st = new StringTokenizer(br.readLine());
        taxi = new Taxi(gas, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            // 나중에 dest에서 목적지 찾기 위해 i번째 택시를 -i로 표시
            map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = -i;
            dest[i][0] = Integer.parseInt(st.nextToken());
            dest[i][1] = Integer.parseInt(st.nextToken());
        }

        int cnt = M;
        // M명 찾아 목적지로 보낼때까지 while문
        while (cnt-- > 0) {
            if (!find()) break;
        }
        if (cnt == -1) System.out.println(taxi.gas);
        else System.out.println(-1);
    }

	// 현재 가스 내 범위에서 손님 찾을 수 있으면 true 리턴
    static boolean find() {
        boolean[][] visited = new boolean[N+1][N+1];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {taxi.row, taxi.col});
        visited[taxi.row][taxi.col] = true;
        Person p = null;
        int dist = 0;
        // 현재 위치에 손님이 있다면: 바로 태우고, bfs는 실행하지 않음
        if (map[taxi.row][taxi.col] < 0) {
            queue.poll();
            p = new Person(-map[taxi.row][taxi.col], taxi.row, taxi.col);
        }
        while (!queue.isEmpty()) {
            if (p != null) break;
            dist++;
            int size = queue.size();
            while (size-- > 0) {
                int[] temp = queue.poll();
                int r = temp[0], c = temp[1];
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;
                    if (visited[nr][nc] || map[nr][nc] == 1) continue;
                    if (map[nr][nc] < 0) {
                    	// 같은 거리일 경우, row, col이 작은 손님 태우기
                        if (p == null || p.row > nr || (p.row == nr && p.col > nc)) {
                            p = new Person(-map[nr][nc], nr, nc);
                        }
                    }
                    visited[nr][nc] = true;
                    queue.offer(new int[] {nr, nc});
                }
            }
        }
		
        // 손님을 못 찾았거나, 가스가 부족한 경우
        if (p == null || taxi.gas < dist) return false;
        taxi.gas -= dist;
        taxi.row = p.row;
        taxi.col = p.col;
        map[taxi.row][taxi.col] = 0;
        return move(p.num);
    }

	// 손님 위치에서 해당 손님 목적지까지 갈 수 있으면 true 리턴
    static boolean move(int num) {
        int targetR = dest[num][0], targetC = dest[num][1];
        boolean[][] visited = new boolean[N+1][N+1];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {taxi.row, taxi.col});
        visited[taxi.row][taxi.col] = true;
        int dist = 0;
        boolean reached = false;
        outer: while (!queue.isEmpty()) {
            dist++;
            int size = queue.size();
            while (size-- > 0) {
                int[] temp = queue.poll();
                int r = temp[0], c = temp[1];
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;
                    if (visited[nr][nc] || map[nr][nc] == 1) continue;
                    if (nr == targetR && nc == targetC) {
                        reached = true;
                        break outer;
                    }
                    visited[nr][nc] = true;
                    queue.offer(new int[] {nr, nc});
                }
            }
        }
	
    	// 목적지에 도착하지 못했거나, 가스가 모자란 경우
        if (!reached || taxi.gas < dist) return false;
        taxi.gas += dist;
        taxi.row = targetR;
        taxi.col = targetC;
        return true;
    }


    static class Taxi {
        int gas;
        int row;
        int col;

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

    static class Person {
        int num;
        int row;
        int col;

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

}