백준 19328번 : 스타트 택시 [Java]

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

 

문제 탐색하기

또 다른 구현 문제를 만났다. 지문이 길긴 하지만 잘 읽어보면 아래와 같은 순서로 구현하면 된다는 것을 알 수 있다.

1. 현재 위치에서 최단거리가 가장 짧은 승객을 고른다 (최단 거리가 같을 시, 가장 작은 행 / 가장 작은 열 번호의 승객)
2. 해당 위치로 이동 시키고 연료를 소모한다. 이동 중 연료 양을 지속적으로 확인하는 로직을 추가한다.
3. 목적지에 도착하면 소모한 연료 양의 두 배를 충전한다.

위를 모든 승객을 태울 때까지 반복하고 이후에 남은 연료 양을 출력하면 되는 문제이다.

 

1번과 같은 경우 매번 최단 거리를 계산 해야하기 때문에 우리는 모든 승객의 좌표가 필요하고, 해당 승객의 탑승 여부 또한 확인해야한다.

2번과 같은 경우 bfs로 구현하면 되고 이동 중 연료 양을 확인하는 로직은 중간 중간 계산할 필요 없이 실제 목적지까지 이동 후에 이동할때 소모한 연료의 양이 남은 연료 양보다 작거나 같은지 확인하면 된다.

 

코드 구현하기

1. 입력을 처리한 후 2차원 배열을 통해서 지도를 표시한다.
2. 아래와 같은 반복문을 통해서 모든 승객에 대한 탑승을 순서대로 처리한다.
   1. 현재 위치에서 제일 가까운 승객을 구한다. 이 때 벽이 존재하므로 bfs와 같은 방법을 통해서 직접 탐색해야한다.
   2. 제일 가까운 승객의 좌표까지 이동한 후 연료를 소모한다.
   3. 승객의 목적지까지 이동한다. 이후 연료를 소모할 수 있으면 소모하고 그렇지 않으면 탐색을 멈춘다.
   4. 목적지에 성공적으로 도달하면 목적지로 이동할 때 사용한 연료 양의 2배를 돌려받는다.
3. 모든 승객을 태우는데 성공하거나 연료가 부족해서 탐색을 멈춘다면 남은 연료 양을 출력한다.

풀이

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

class Main {
    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
    
    static int N, M, F, SX, SY;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] graph;
    static boolean[][] visited;
    static boolean[][] pickUpVisited;
    static boolean[][] customerVisited;
    static HashMap<Node, Customer> customers = new HashMap<>();

    static class Customer {
        int cx, cy, tx, ty;
        int requiredFuel;

        public Customer(int cx, int cy, int tx, int ty) {
            this.cx = cx;
            this.cy = cy;
            this.tx = tx;
            this.ty = ty;
            this.requiredFuel = -1;
            bfs();
        }

        public void bfs() {
            visited = new boolean[N][N];
            LinkedList<Node> q = new LinkedList<>();

            visited[cx][cy] = true;
            q.add(new Node(cx, cy, 0));

            while (!q.isEmpty()) {
                Node node = q.poll();
                if (node.x == tx && node.y == ty) {
                    this.requiredFuel = node.count;
                    return;
                }

                for (int i = 0; i < 4; i++) {
                    int nx = node.x + dx[i];
                    int ny = node.y + dy[i];
                    if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                        if (!visited[nx][ny] && graph[nx][ny] != 1) {
                            q.add(new Node(nx, ny, node.count + 1));
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }
    }

    static class Node {
        int x, y, count;

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

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

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Node node = (Node)o;
            return x == node.x && y == node.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getCount() {
            return count;
        }
    }

    private static Node pickUp() {
        pickUpVisited = new boolean[N][N];
        ArrayList<Node> result = new ArrayList<>();
        LinkedList<Node> q = new LinkedList<>();
        visited[SX][SY] = true;
        q.add(new Node(SX, SY, 0));

        while (!q.isEmpty()) {
            Node node = q.poll();
            if (graph[node.x][node.y] == 2 && customers.containsKey(node)) {
                if (F - node.count >= 0 && !result.contains(node)) {
                    result.add(node);
                }
            }

            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    Node now = new Node(nx, ny, node.count + 1);
                    if (graph[nx][ny] != 1 && !pickUpVisited[nx][ny]) {
                        q.add(now);
                        pickUpVisited[nx][ny] = true;
                    }
                }
            }
        }

        Collections.sort(result, Comparator.comparing(Node::getCount).thenComparing(Node::getX).thenComparing(Node::getY));

        Node node = null;
        if (!result.isEmpty()) {
            node = result.get(0);
            customerVisited[node.x][node.y] = true;
        }
        return node;
    }

    public static void main(String[] args) {
        FastReader fr = new FastReader();

        N = fr.nextInt();
        M = fr.nextInt();
        F = fr.nextInt();

        graph = new int[N][N];
        customerVisited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = fr.nextInt();
            }
        }

        SX = fr.nextInt() - 1;
        SY = fr.nextInt() - 1;

        for (int i = 0; i < M; i++) {
            int cx = fr.nextInt() - 1, cy = fr.nextInt() - 1;
            int tx = fr.nextInt() - 1, ty = fr.nextInt() - 1;
            graph[cx][cy] = 2;
            customers.put(new Node(cx, cy), new Customer(cx, cy, tx, ty));
        }


        while (M != 0) {
            Node next = pickUp();
            if (next != null) {
                F -= next.count;
                Customer now = customers.get(next);

                if (F - now.requiredFuel < 0 || now.requiredFuel == -1) {
                    break;
                } else {
                    M--;
                    F += now.requiredFuel;
                    SX = now.tx;
                    SY = now.ty;
                    customers.remove(next);
                }
            } else {
                break;
            }
        }

        System.out.println(M == 0 ? F : -1);
    }
}