백준19238.스타트 택시 - JAVA, 구현, HashMap, List, BFS

 

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

 

 

 

 

 

코드 & 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
* 1. 손님별 택시와 최단 거리 구하기 -> BFS
* -> 거리별 > 행 번호 > 열 번호
* 2. 나온 거리를 택시가 갈 수 있는지 확인
* 가능 => 연료 계산
* 불가능 => return -1
* */
public class 백준_스타트택시_19238 {
    static int N, M, fuel;
    static int[][] city;
    static Taxi taxi;
    static Map<Position, Passenger> passengers = new HashMap<>();
    static int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 하 좌 우

    static class Position {
        int x;
        int y;

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

        @Override
        public boolean equals(Object o) {
            Position p = (Position) o;
            return x == p.x && y == p.y;
        }

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

    static class Passenger {
        Position start;
        Position end;

        Passenger(Position start, Position end) {
            this.start = start;
            this.end = end;
        }
    }

    static class Taxi {
        Position pos;

        Taxi(int x, int y) {
            this.pos = new Position(x, y);
        }
    }

    static class Node implements Comparable<Node> {
        int x;
        int y;
        int dist;

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

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

    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()); // 최초 연료

        city = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        int taxi_x = Integer.parseInt(st.nextToken()) - 1;
        int taxi_y = Integer.parseInt(st.nextToken()) - 1;
        taxi = new Taxi(taxi_x, taxi_y);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start_x = Integer.parseInt(st.nextToken()) - 1;
            int start_y = Integer.parseInt(st.nextToken()) - 1;
            int end_x = Integer.parseInt(st.nextToken()) - 1;
            int end_y = Integer.parseInt(st.nextToken()) - 1;
            passengers.put(new Position(start_x, start_y), new Passenger(new Position(start_x, start_y), new Position(end_x, end_y)));
        }

        for (int i = 0; i < M; i++) {
            Node nearest = findNearestPassenger();
            if (nearest == null || nearest.dist > fuel) {
                System.out.println(-1);
                return;
            }

            fuel -= nearest.dist;
            taxi.pos = new Position(nearest.x, nearest.y);
            Passenger p = passengers.get(taxi.pos);
            passengers.remove(taxi.pos);

            int distToDest = moveToDestination(p.end);
            if (distToDest == -1 || distToDest > fuel) {
                System.out.println(-1);
                return;
            }

            fuel += distToDest;
            taxi.pos = p.end;
        }

        System.out.println(fuel);
    }

    static Node findNearestPassenger (){
        boolean[][] visited = new boolean[N][N];
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(taxi.pos.x, taxi.pos.y, 0));
        visited[taxi.pos.x][taxi.pos.y] = true;

        List<Node> candiates = new ArrayList<>();
        int minDist = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            if (passengers.containsKey(new Position(cur.x, cur.y))) {
                if (cur.dist < minDist) {
                    candiates.clear();
                    minDist = cur.dist;
                }
                if (cur.dist == minDist) {
                    candiates.add(cur);
                }
            }

            for (int[] d : direct) {
                int nx = cur.x + d[0];
                int ny = cur.y + d[1];

                if (isInBounds(nx, ny) && !visited[nx][ny] && city[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.offer(new Node(nx, ny, cur.dist + 1));
                }
            }
        }

        if (candiates.isEmpty()) return null;
        Collections.sort(candiates);
        return candiates.get(0);
    }

    static int moveToDestination(Position dest) {
        boolean[][] visited = new boolean[N][N];
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(taxi.pos.x, taxi.pos.y, 0));
        visited[taxi.pos.x][taxi.pos.y] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.x == dest.x && cur.y == dest.y) {
                return cur.dist;
            }

            for (int[] d : direct) {
                int nx = cur.x + d[0];
                int ny = cur.y + d[1];

                if (isInBounds(nx, ny) && !visited[nx][ny] && city[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.offer(new Node(nx, ny, cur.dist + 1));
                }
            }
        }

        return -1;
    }

    static boolean isInBounds(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}ll

 

 

구현은 문제에서 말하는 과정을 그대로 따라가면 되는 문제라고 생각합니다.

 

근데 문제는 그걸 하기 위해 코드의 구성을 어떻게 할지가 중요하다고 생각해요잉.

 

이 문제에서 했던 고민은

 

1. 승객의 탑승 위치, 도착 위치를 어떻게 형식으로 저장할지

2. 택시가 가장 가까운 승객을 어떻게 판별할지

3. 가장 가까운 승객이 어떤 승객인지 어떻게 구별할 것인지

 

이정도인 것 같아요.

 

이걸 해결하기 위해 클래스를 선언해서

 

시작, 도착 위치를 저장했고,

 

승객은 HashMap으로 탐색했습니다.

 

이후에는

 

1. 택시와 가장 가까운 승객 찾기 -> BFS

 

2. 승객의 도착지 탐색 -> BFS

2-1) 도착지까지의 거리가 남은 연료보다 많으면 return -1

2-2) 연료가 남으면

 

fuel -=distToDest

fuel += (distToDest * 2)

이기에

 

fuel += distToDest로 뚱칩니다.

 

3. 택시 위치를 승객의 도착지로 변경

 

4. 1로 이동

 

 

 

 

 

 

 

다음에 또 봐요