[백준]#19238 스타트 택시

문제

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

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

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

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 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을 출력한다.

예제 입력 1

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

예제 출력 1

14

예제 입력 2

6 3 13
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

예제 출력 2

-1

예제 입력 3

6 3 100
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 1 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

예제 출력 3

-1

풀이

이 문제는 BFS 알고리즘을 이용해서 손님을 태울 수 있는 지와 목적지로 이동 가능한지를 체크하고 연료를 체크해서 답을 구했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static Customer[] list;
    static Taxi taxi;
    static boolean[] visited;
    static int N;
    static int M;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        int fuel = Integer.parseInt(input[2]);
        map = new int[N+1][N+1];
        list = new Customer[M];
        visited = new boolean[M];

        for(int i=1; i<=N; i++) {
            input = br.readLine().split(" ");
            for(int j=1; j<=N; j++)
                map[i][j] = Integer.parseInt(input[j-1]);
        }

        input = br.readLine().split(" ");

        taxi = new Taxi(Integer.parseInt(input[0]), Integer.parseInt(input[1]), fuel);

        for(int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            list[i] = new Customer(Integer.parseInt(input[0]), Integer.parseInt(input[1]), Integer.parseInt(input[2]), Integer.parseInt(input[3]));
        }

        solution();
    }
    
    public static int bfs(int x, int y, int r, int c) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited2 = new boolean[N+1][N+1];
        visited2[x][y] = true;
        queue.add(new Pair(x, y, 0));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(temp.x==r && temp.y==c) {
                return temp.d;
            }

            for(int i=0; i<4; i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];

                if(nx<=0 || nx>N || ny<=0 || ny>N || visited2[nx][ny] || map[nx][ny]==1) continue;

                visited2[nx][ny] = true;
                queue.add(new Pair(nx, ny, temp.d+1));
            }
        }

        return Integer.MAX_VALUE;
    }

    public static void solution() {
        boolean flag = false;

        loop:while(true) {
            int min_index = Integer.MAX_VALUE;
            int min = Integer.MAX_VALUE-1;

            for(int i=0; i<M; i++) {
                if(!visited[i]) {
                    int len = bfs(taxi.x, taxi.y, list[i].x, list[i].y);
                    if(len==Integer.MAX_VALUE) break loop;

                    if(min>=len) {
                        if(min==len) {
                            if(list[min_index].x>list[i].x) {
                                min = len;
                                min_index = i;
                            }

                            else if(list[min_index].x==list[i].x) {
                                if(list[min_index].y>list[i].y) {
                                    min = len;
                                    min_index = i;
                                }
                            }
                        }

                        else {
                            min = len;
                            min_index = i;
                        }
                    }
                }
            }

            if(min==Integer.MAX_VALUE-1) {flag = true; break;}

            visited[min_index] = true;
            int using_fuel = min + bfs(list[min_index].x, list[min_index].y, list[min_index].r, list[min_index].c);

            if(using_fuel>taxi.f) {
                System.out.println(-1);
                return;
            }

            taxi = new Taxi(list[min_index].r, list[min_index].c, taxi.f-using_fuel+2*(using_fuel-min));
        }

        if(!flag)
            System.out.println(-1);
        else
            System.out.println(taxi.f);
    }

    public static class Pair {
        int x;
        int y;
        int d;

        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public static class Taxi {
        int x;
        int y;
        int f;

        public Taxi(int x, int y, int f)  {
            this.x = x;
            this.y = y;
            this.f = f;
        }
    }

    public static class Customer {
        int x;
        int y;
        int r;
        int c;

        public Customer(int x, int y, int r, int c)  {
            this.x = x;
            this.y = y;
            this.r = r;
            this.c = c;
        }
    }
}