BJ G4 19238 스타트택시

BJ G4 19238 스타트택시

 

 

문제링크

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

19238번: 스타트 택시

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

• M 명의 손님을 목적지로 이동시킴 따라서 M 번 손님 선택 --> 목적지 이동을 반복 

• 손님 선택 기준: 1. 가장 가까운 위치의 손님 2. 1이 같다면 행 번호가 가장 작은 손님, 2도 같다면 열 번호가 가장 작은 손님 

• 1칸을 이동할 때마다 연료는 1씩 감소, 연료의 양이 0이 되면 이동 중지 

• 손님을 이동시킨 후는 자리를 0으로 만들어줄 것 

• 도착지에서 즉시 손님을 태울 수 있음

입력사항

• 지도의 크기: N×N (2 ≤ N ≤ 20) 지도에서 0은 빈칸, 1은 벽 

• 1 ≤ 초기 연료 ≤ 500,000 이며 연료통은 무한 

• 손님을 태운 후 이동한 거리의 두 배가 충전됨(손님을 태우러 갈때는 빼고) 

• 승객 수 M 1 ≤ M ≤ N^2

출력사항

• 모든 손님을 이동시키고 충전했을 때 남은 연료의 양 출력 

• 손님이 남아있다면 -1 출력

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=RaTGBFbJiZU

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G4_19238_스타트택시 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static int N, M, K;
    static int[][] map;
    static Point[] dests;
    static int startR, startC;

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

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        StringTokenizer tokens = new StringTokenizer(input.readLine());
        // 지도의 index들이 1부터 시작
        N = Integer.parseInt(tokens.nextToken()) + 1; // 지도 크기
        M = Integer.parseInt(tokens.nextToken()); // 고객 수
        K = Integer.parseInt(tokens.nextToken()); // 연료 량

        map = new int[N][N];
        for (int r = 1; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 1; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }

        tokens = new StringTokenizer(input.readLine());
        startR = Integer.parseInt(tokens.nextToken());
        startC = Integer.parseInt(tokens.nextToken());

        // 목적지 정보
        dests = new Point[M + 2];
        // 0과 1은 이미 사용 중이므로 고객은 2번부터로 표시
        for (int i = 2; i < M + 2; i++) {
            tokens = new StringTokenizer(input.readLine());
            // 앞에 두 개의 정보인 손님은 지도에 표시하고
            map[Integer.parseInt(tokens.nextToken())][Integer.parseInt(tokens.nextToken())] = i;
            // 뒤에 두 개의 정보인 목적지는 별도의 배열에 저장
            dests[i] = new Point(Integer.parseInt(tokens.nextToken()), Integer.parseInt(tokens.nextToken()));
        }

        /*for (int[] row : map) {
            System.out.println(Arrays.toString(row));
        }*/

        boolean fail = false;
        // M 명의 고객을 처리하면 된다. 중간에 실패하면 가볼 필요 없다.
        for (int m = 0; m < M; m++) {
            Taxi taxi = findPassenger();
            // m 번 내에 손님을 못찾으면 실패
            if (taxi == null) {
                fail = true;
                break;
            }
            // 손님 태운 위치는 공백으로 수정
            map[taxi.row][taxi.col] = 0;

            // System.out.println(m + "번째 손님 탑승: " + taxi);
            taxi = toDest(taxi);
            if (taxi == null) {
                fail = true;
                break;
            }
            // System.out.println(m + "번째 손님 하차: " + taxi);
        }
        System.out.println(fail ? -1 : K);
    }

    static Taxi findPassenger() {
        // 현재 위치가 출발점인 경우
        if (map[startR][startC] > 1) {
            return new Taxi(startR, startC, K, map[startR][startC]);
        }

        PriorityQueue<Taxi> pq = new PriorityQueue<>();
        Queue<Taxi> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];

        Taxi st = new Taxi(startR, startC, K, 0);
        q.offer(st);
        visited[startR][startC] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                Taxi front = q.poll();
                // 택시에 연료가 없다면 땡!!
                if (front.fuel == 0) {
                    return null;
                }
                for (int d = 0; d < 4; d++) {
                    int nr = front.row + dirs[d][0];
                    int nc = front.col + dirs[d][1];
                    if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) {
                        visited[nr][nc] = true;
                        if (map[nr][nc] > 1) {
                            pq.offer(new Taxi(nr, nc, front.fuel - 1, map[nr][nc]));
                        } else {
                            q.offer(new Taxi(nr, nc, front.fuel - 1, 0));
                        }
                    }
                }
            }
            if (pq.size() > 0) {
                return pq.poll();
            }
        }
        return null;
    }

    static Taxi toDest(Taxi taxi) {
        // 손님의 목적지까지 가기 전에 기본 연료 량
        int baseFuel = taxi.fuel;
        Point target = dests[taxi.passNo];
        // System.out.println("목적지 출발: " + taxi + ",목적지: " + target);
        Queue<Taxi> q = new LinkedList<>();
        q.offer(taxi);

        boolean[][] visited = new boolean[N][N];
        visited[taxi.row][taxi.col] = true;

        while (!q.isEmpty()) {
            Taxi front = q.poll();
            if (front.fuel == 0) {
                return null;
            }
            for (int d = 0; d < dirs.length; d++) {
                int nr = front.row + dirs[d][0];
                int nc = front.col + dirs[d][1];

                if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) {
                    visited[nr][nc] = true;
                    Taxi nextTaxi = new Taxi(nr, nc, front.fuel - 1, front.passNo);
                    if (nr == target.row && nc == target.col) {
                        // 좌표 처리 하고
                        startR = nr;
                        startC = nc;
                        // 기름 정산
                        K = nextTaxi.fuel + (baseFuel - nextTaxi.fuel) * 2;
                        // System.out.println("정산 정보: 남은 기름:" + K);
                        return nextTaxi;
                    }
                    q.offer(nextTaxi);
                }
            }
        }
        return null;
    }

    static boolean isIn(int r, int c) {
        return 1 <= r && r < N && 1 <= c && c < N;
    }

    static class Point {
        int row, col;

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

        @Override
        public String toString() {
            return "[row=" + row + ", col=" + col + "]";
        }
    }

    static class Taxi implements Comparable<Taxi> {
        int row, col;
        int fuel;
        int passNo;

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

        @Override
        public int compareTo(Taxi o) {
            // 거리가 같다면 row가 작은 녀석
            if (this.fuel == o.fuel) {
                // row가 같다면 col이 작은 녀석
                if (this.row == o.row) {
                    return Integer.compare(this.col, o.col);
                } else {
                    return Integer.compare(this.row, o.row);
                }
            }
            // 가까운 위치의 녀석이니까 내림차순
            else {
                return Integer.compare(o.fuel, this.fuel);
            }
        }

        @Override
        public String toString() {
            return "[(" + row + "," + col + "), fuel=" + fuel + ", passNo=" + passNo + "]";
        }

    }

    private static String src = "6 4 14\r\n" +
                                "0 0 1 0 0 0\r\n" +
                                "0 0 1 0 0 0\r\n" +
                                "0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0\r\n" +
                                "0 0 0 0 1 0\r\n" +
                                "0 0 0 1 0 0\r\n" +
                                "6 5\r\n" +
                                "2 2 5 6\r\n" +
                                "5 4 1 6\r\n" +
                                "4 2 3 5\r\n" +
                                "1 6 5 4";
}