[백준 19238] 스타트 택시 - JAVA

과거에 풀었던 문제입니다. 노션에 기록된 내용을 바탕으로 정리했습니다.

문제 정의

• N×N 크기의 격자에 M명의 승객
• 택시는 한 칸마다 상/하/좌/우로 이동 가능.
• 0은 빈 칸, 1은 벽이며, 벽은 통과할 수 없음.
• 택시는 연료를 가지고 있고, 승객을 태우고 목적지까지 데려다 주면 연료가 충전됨.
• 목표는 모든 승객을 이동시키는 것이며, 중간에 연료가 떨어지면 실패.

출력

• 모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력
• 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력
• 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

접근 방법

• Passenger라는 클래스를 생성하고 특정 승객에 대해서 출발점sy sx과 도착점 ey ex 지정

  • 입력 받을 때 입력받은 영역area에 따른 거리를 계산하는 setDist 선언

    • setDist 는 BFS를 활용해 시작 점에서부터 도착 지점까지 탐색해나갑니다.

      

    • 만약 탐색하지 못하는 경우 → 목적지까지 도달하지 못하는 경우 → IsPossible을 False로 변경

    • isPossible 을 통해서 승객들을 모두 목적지까지 도달할 수 있는지 여부를 setDist를 하는 과정에서 빠르게 판단해 연산을 줄이는 역할입니다.

  • 0은 이동할 수 있는 공간, 1은 벽을 의미하므로 2부터 2 + M까지 승객으로 시작 위치를 area에 저장

    • 승객의 정보를 저장
      - sy: 시작 좌표 y축, sx: 시작 좌표 x축, ey: 종료 좌표 y축, ex: 종료 좌표 x축
      - dist 시작 좌표로부터 종료 좌표까지의 거리
      
    • 승객의 정보는 2부터 시작하므로 passengers 안에 dummy input을 2개 추가

• CanPickupAllPassengers 메소드를 구현해서 모두 태울 수 있는지 여부에 따라 -1 또는 연료의 남은 양을 출력

  • 택시의 현재 위치로부터 가장 가까운 승객 위치로 이동 → findPassenger 수행
    • findPassenger 는 현재 위치로부터 가장 가까운 승객의 위치를 찾아서 좌표를 변경하는 로직
    • 이 때 가장 가까운 승객이 여러 명일 경우 → 가장 위에 있는 순서부터 → 가장 오른쪽에 있는 순서부터 선택
  • 연료의 양을 확인하고 승객까지 이동하는 거리 + 승객이 목적지까지 이동하는 거리가 연료의 남은 양에 따라 로직 수행
    • 연료의 남은 양이 더 많을 경우: 남은 연료량에서 승객까지 이동하는 거리를 빼주고 승객이 목적지까지 이동하는 거리를 더해줍니다.
    • 연료가 부족한 경우: -1을 반환하고 로직을 종료

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 승객 클래스 (시작 좌표, 종료 좌표, 종료 좌표까지의 거리를 저장)
class Passenger {
    int sy;
    int sx;
    int ey;
    int ex;
    int dist;

    public Passenger(int sy, int sx, int ey, int ex, int dist) {
        this.sy = sy;
        this.sx = sx;
        this.ey = ey;
        this.ex = ex;
        this.dist = dist;
    }
}

public class Main {
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int M;
    static int F;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());
        int[][] area = new int[N][N];
        boolean isPossible = true;    // 모든 승객에 대해서 dist를 구할 수 있는지 여부

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

        st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken()) - 1;
        int x = Integer.parseInt(st.nextToken()) - 1;

				// 승객들의 정보를 리스트로 저장(0은 빈 공간, 1은 벽이므로 2개의 더미 입력 추가)
				// 입력으로 들어오는 승객 정보는 2번 인덱스부터 기록하고
				// area 2차원 배열에서 시작 좌표를 인덱스로 변경 
        ArrayList<Passenger> passengers = new ArrayList<>();
        // dummy input
        passengers.add(new Passenger(0, 0, 0, 0, 0));
        passengers.add(new Passenger(0, 0, 0, 0, 0));

        for (int i = 2;  i < M + 2; i++) {
            st = new StringTokenizer(br.readLine());
            int sy = Integer.parseInt(st.nextToken()) - 1;
            int sx = Integer.parseInt(st.nextToken()) - 1;
            int ey = Integer.parseInt(st.nextToken()) - 1;
            int ex = Integer.parseInt(st.nextToken()) - 1;
            int dist = setDist(sy, sx, ey, ex, area);
            
            // 승객의 목적지가 도달할 수 없는 곳에 존재한다면
            // isPossible을 false로 변경하고 break 
            if (dist == -1) {
                isPossible = false;
                break;
            }
            // 정상적인 경우 승객의 정보를 리스트에 저장하고 시작 좌표를 passenger의 index로 수정
            passengers.add(new Passenger(sy, sx, ey, ex, dist));
            area[sy][sx] = i;
        }
        if (isPossible) System.out.println(canPickUpAllPassengers(y, x, passengers, area));
        else System.out.println(-1);
    }

		// Passenger 클래스의 dist를 구하기 위한 BFS 메소드
    static int setDist(int sy, int sx, int ey, int ex, int[][] area) {
        boolean[][] visited = new boolean[N][N];
        visited[sy][sx] =true;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sy, sx, 0});

        while (!q.isEmpty()) {
            int[] node = q.poll();
            int y = node[0];
            int x = node[1];
            int dist = node[2];


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

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

                if (0 <= ny && ny < N && 0 <= nx && nx < N && !visited[ny][nx] && area[ny][nx] != 1) {
                    visited[ny][nx] = true;
                    q.offer(new int[]{ny, nx, dist + 1});
                }
            }
        }
        // 승객의 목적지까지 도달할 수 없는 경우 -1 반환
        return -1;
    }

    static int canPickUpAllPassengers(int y, int x, ArrayList<Passenger> passengers, int[][] area) {
        int restPassenger = M;
        while (restPassenger --> 0) {
            // 승객 정보를 가져오기
            int[] passengerInfo = findPassenger(y, x, area);

            // null일 경우 반환
            if (passengerInfo == null) return -1;

            // 승객 정보 가져오기
            Passenger passenger = passengers.get(passengerInfo[1]);

            // 이동 거리만큼 감소
            F -= passengerInfo[0];

            // 승객한테 이동하는 도중 연료가 고갈될 경우
            if (F < 0) return -1;

            // 승객부터 목적지까지 도달하지 못하는 경우
            if (F - passenger.dist < 0) return -1;

            // 연료 증가
            F += passenger.dist;

            // 좌표 변경
            y = passenger.ey;
            x = passenger.ex;

            // 이미 처리된 승객을 제거
            area[passenger.sy][passenger.sx] = 0;
        }

				// 모든 승객을 이동시킬 수 있다면 연료의 잔량을 반환
        return F;
    }


		// 현재 택시의 위치로부터 가장 가까운 승객을 찾는 메서드 (BFS)
    static int[] findPassenger(int sy, int sx, int[][] area) {
        boolean[][] visited = new boolean[N][N];
        visited[sy][sx] =true;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sy, sx, 0});
        while (!q.isEmpty()) {
            int size = q.size();

            while (size --> 0) {
                int[] node = q.poll();
                int y = node[0];
                int x = node[1];
                int dist = node[2];

                if (area[y][x] >= 2) {
                    while (!q.isEmpty()) {
                        node = q.poll();
                        int ny = node[0];
                        int nx = node[1];
                        int newDist = node[2];

                        if (area[ny][nx] >= 2 && dist == newDist) {
                            if ((y > ny) || (y == ny && x > nx)) {
                                y = ny;
                                x = nx;
                            }
                        }
                    }
                    // 택시의 현재 위치에서 승객까지의 거리와 인덱스 좌표를 반환
                    return new int[]{dist, area[y][x]};
                }

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

                    if (0 <= ny && ny < N && 0 <= nx && nx < N && !visited[ny][nx] && area[ny][nx] != 1) {
                        visited[ny][nx] = true;
                        q.offer(new int[]{ny, nx, dist + 1});
                    }
                }
            }
        }
        return null;
    }
}