[백준 19238 JAVA] 스타트 택시

 

 

dfs를 활용한 구현문제이다.

 

PriorityQueue를 활용해 가장 가까운, 거리가 같다면 행번호가 적은, 행도 같다면 열번호가 적은 승객을 구해 이동시킨다.

그 후 해당 승객이 원하는 지점에 데려다준다.

 

위의 과정을 계속 반복하면 된다.

 

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

class Point {
    public int y, x;

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

class Move implements Comparable<Move> {
    public int y, x;
    public int cost;

    public Move(int y, int x, int cost) {
        this.y = y;
        this.x = x;
        this.cost = cost;
    }

    @Override
    public int compareTo(Move o) {
        if (this.cost != o.cost) return this.cost - o.cost;
        if (this.y != o.y) return this.y - o.y;
        return this.x - o.x;
    }
}

public class Main {
    static int N, M, FUEL;
    static boolean[][] map;
    static Point[][] Passengers;
    static PriorityQueue<Move> pq;
    static Queue<Move> q;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};

    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());
        FUEL = Integer.parseInt(st.nextToken());
        map = new boolean[N + 1][N + 1];
        Passengers = new Point[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                if (st.nextToken().equals("1")) {
                    map[i][j] = true;
                }
            }
        }
        st = new StringTokenizer(br.readLine());
        int startTaxiY = Integer.parseInt(st.nextToken());
        int startTaxiX = Integer.parseInt(st.nextToken());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int startY = Integer.parseInt(st.nextToken());
            int startX = Integer.parseInt(st.nextToken());
            int destY = Integer.parseInt(st.nextToken());
            int destX = Integer.parseInt(st.nextToken());
            Passengers[startY][startX] = new Point(destY, destX);
        }

        while (M-- != 0) {
            Move passenger = findPassenger(startTaxiY, startTaxiX);
            if (passenger.x == 0) {
                System.out.println(-1);
                return;
            }
            FUEL -= passenger.cost;
            Move goal = goGoal(passenger.y, passenger.x);
            if (goal.x == 0) {
                System.out.println(-1);
                return;
            }
            FUEL -= goal.cost;
            FUEL += (goal.cost * 2);
            startTaxiY = goal.y;
            startTaxiX = goal.x;
        }
        System.out.println(FUEL);
    }

    static Move goGoal(int y, int x) {
        q = new ArrayDeque<>();
        boolean[][] visit = new boolean[N + 1][N + 1];
        visit[y][x] = true;
        int goalY = Passengers[y][x].y;
        int goalX = Passengers[y][x].x;
        Passengers[y][x] = null;
        q.offer(new Move(y, x, 0));
        while (!q.isEmpty()) {
            Move cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextY = cur.y + dy[i];
                int nextX = cur.x + dx[i];
                if (nextY > N || nextY <= 0 || nextX > N || nextX <= 0 || visit[nextY][nextX] || map[nextY][nextX])
                    continue;
                visit[nextY][nextX] = true;
                if (cur.cost + 1 > FUEL) break;
                Move temp = new Move(nextY, nextX, cur.cost + 1);
                if (nextY == goalY && nextX == goalX) {
                    return temp;
                }
                q.add(temp);
            }
        }
        return new Move(0, 0, 0);
    }

    static Move findPassenger(int y, int x) {
        pq = new PriorityQueue<>();
        boolean[][] visit = new boolean[N + 1][N + 1];
        //승객을 찾기 시작하는 자리에 승객이 있으면 자기 위치 반환
        if (Passengers[y][x] != null) {
            return new Move(y, x, 0);
        }
        pq.offer(new Move(y, x, 0));
        Move value = new Move(0, 0, 0);

        while (!pq.isEmpty()) {
            Move cur = pq.poll();
            if (Passengers[cur.y][cur.x] != null) {
                return new Move(cur.y, cur.x, cur.cost);
            }
            for (int i = 0; i < 4; i++) {
                int nextY = cur.y + dy[i];
                int nextX = cur.x + dx[i];
                if (nextY > N || nextY <= 0 || nextX > N || nextX <= 0 || visit[nextY][nextX] || map[nextY][nextX])
                    continue;
                visit[nextY][nextX] = true;
                if (cur.cost + 1 > FUEL) break;
                pq.add(new Move(nextY, nextX, cur.cost + 1));

            }
        }
        return value;
    }
}