[백준] 19238. 스타트 택시 (Java)

 

19238번: 스타트 택시

 

풀이

• 시간초과가 났던 문제. 검색하여 찾아보니 연료를 무한으로 충전할 수 있어서 그렇다고 한다.
• 문제에는 적혀있지 않은 예외사항이 두 가지 있다.
  1. 택시 기사가 승객의 위치까지 도달할 수 없는 경우 (거리 = INF)
  2. 승객을 도착지까지 태울 수 없는 경우 (거리 = INF)
• 되는지 안되는지 판단할 때 단순히 거리와 연료량 여부로 판단하면 안되고 이 부분도 고려해야 문제가 통과한다.

 

 

---

 

• 구현문제라 문제에 충실하면 생각보다 어렵지 않은 문제이다.
• 사람마다 풀이가 약간씩 다르지만 나는 다음과 같이 구현했다.
• 출발 좌표 (x, y), 거리, 도착 좌표 (ex, ey)를 parameter로 가지는 custom class Passenger를 구현했다.
  • HashMap을 사용할 것이기 때문에 추가로 equals, hashCode method를 overriding 했다.
• 승객 정보를 HashMap<Passenger, Boolean>에 구현했다.
• while (M-- > 0) 으로 반복문을 돈다.

1. 택시기사 주변 승객 정보를 업데이트한다. (updatePassengerList())
   • HashMap의 keyset을 돌며 각 승객별 택시기사 - 승객까지의 거리를 우선순위큐에 넣는다.
   • getDist(출발 좌표, 도착 좌표)로 거리를 구해온다.
2. 우선순위큐에서 가장 앞에 있는 승객을 뽑고, HashMap에서 해당 승객을 지운다.

3-1. 택시기사 -> 승객위치까지의 거리 < 현재 연료량이거나 거리 == INF이면 -1을 출력 후 종료한다.
3-2. 택시기사 -> 승객 위치까지의 거리 >= 현재 연료량이면

• 승객을 출발 -> 도착지까지 태우는 거리 >= 현재연료 - 태우는 거리이면 현재 연료에 승객 태운 거리를 더하고 택시기사의 현재 위치를 승객의 도착지로 업데이트 한다.
• 그렇지 않으면 -1을 출력 후 종료한다.

 

 

 

---

 

코드

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

public class Main {
    static int N, M, minDist;
    static long F;
    static boolean[][] map;
    static int[] dx = new int[]{1, 0, -1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    static final int INF = 1000;
    static Passenger taxiDriver = new Passenger(0, 0);
    static HashMap<Passenger, Boolean> passengerList = new HashMap<>();
    static PriorityQueue<Passenger> passengersNearby = new PriorityQueue<>((o1, o2) -> {
        if (o1.dist == o2.dist) {
            if (o1.x == o2.x) {
                return Integer.compare(o1.y, o2.y);
            }
            return Integer.compare(o1.x, o2.x);
        }
        return Integer.compare(o1.dist, o2.dist);
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());

        map = new boolean[N + 1][N + 1];
        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()) == 1 ? true : false;
        }
        st = new StringTokenizer(br.readLine());
        taxiDriver.x = Integer.parseInt(st.nextToken());
        taxiDriver.y = Integer.parseInt(st.nextToken());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int px = Integer.parseInt(st.nextToken());
            int py = Integer.parseInt(st.nextToken());
            int nx = Integer.parseInt(st.nextToken());
            int ny = Integer.parseInt(st.nextToken());

            passengerList.put(new Passenger(px, py, 0, nx, ny), true);
        }

        while (M-- > 0) {
            updatePassengerList();

            int dist = passengersNearby.peek().dist;
            if (dist > F || dist == INF) {
                F = -1;
                break;
            }
            F -= dist;

            int sx = passengersNearby.peek().x;
            int sy = passengersNearby.peek().y;
            int ex = passengersNearby.peek().ex;
            int ey = passengersNearby.peek().ey;
            Passenger p = new Passenger(sx, sy, 0, ex, ey);
            passengerList.remove(p);

            minDist = INF;
            dist = getDist(sx, sy, ex, ey);

            if (dist > F || dist == INF) {
                F = -1;
                break;
            }
            F += dist;
            taxiDriver.x = ex;
            taxiDriver.y = ey;
        }

        bw.write(String.valueOf(F));
        br.close();
        bw.close();
    }

    public static void updatePassengerList() {
        passengersNearby.clear();
        minDist = INF;

        for (Passenger p : passengerList.keySet()) {
            int dist = getDist(taxiDriver.x, taxiDriver.y, p.x, p.y);
            minDist = Math.min(dist, minDist);
            passengersNearby.offer(new Passenger(p.x, p.y, dist, p.ex, p.ey));
        }
    }

    public static int getDist(int sx, int sy, int ex, int ey) {
        boolean[][] visited = new boolean[N + 1][N + 1];
        visited[sx][sy] = true;
        Queue<Passenger> q = new LinkedList<>();
        q.offer(new Passenger(sx, sy, 0));

        while (!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            int dist = q.peek().dist;
            q.poll();

            if (dist > minDist) break;
            if (x == ex && y == ey) return dist;

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

                if (!isIn(nx, ny) || visited[nx][ny]) continue;
                visited[nx][ny] = true;
                q.offer(new Passenger(nx, ny, dist + 1));
            }
        }
        return INF;
    }

    public static boolean isIn(int x, int y) {
        if (x < 1 || x > N || y < 1 || y > N || map[x][y]) return false;
        return true;
    }

    static class Passenger {
        int x;
        int y;
        int dist;
        int ex;
        int ey;

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

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

        public Passenger(int x, int y, int dist, int ex, int ey) {
            this(x, y, dist);
            this.ex = ex;
            this.ey = ey;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;

            Passenger p = (Passenger) obj;
            return (p.x == x && p.y == y && p.dist == dist && p.ex == ex && p.ey == ey);
        }

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