[BOJ] 19238. 스타트 택시 (🚕, 구현/시뮬레이션)

🔗

풀이

승객을 태운 다음에 목적지까지 이동하는데 항상 모든 경로가 최단거리로 이루어져야 한다. 그래프 탐색 중에서 최단 거리를 가장 빠르게 구할 수 있는 너비 우선 탐색 방식을 이용한다. 너비 우선 탐색은 인접한 정점 순서대로 방문하게 되는데 이때 같은 최단 거리에 여러 승객이 있을 수 있다. 이럴 경우 가장 작은 행, 가장 작은 열을 가진 승객을 태워서 목적지로 이동한다.

처음에는 출발지의 값을 i, 목적지의 값을 -i 로 배열에 직접 입력하고 탐색하는 방식을 사용했는데 아래와 같은 예외 경우들 때문에 목적지를 제대로 찾지 못했다.

1. 모든 출발지는 다르다
2. 모든 승객의 출발지와 목적지는 다르다.
3. A 승객의 출발지와 B 승객의 목적지가 같을 수 있다.

3번 케이스가 발생하면 어떤 승객의 출발지나 목적지가 사라지게 된다. 결국 모든 승객을 태워줄 수 없게 되어서 항상 -1이 나오게 된다. 그래서 승객의 출발지에 대한 정보는 배열에 직접 입력했지만 각 승객에 대한 목적지 정보는 다른 배열에 저장하는 방식으로 해결했다.

// 스타트 택시

package Baekjoon.Gold;

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

public class baekjoon_19238 {
    static int N;
    static int fuel; // 연료
    static int[][] map;
    static int[][] visited;
    static int[][] direction = new int[][] {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    static int[] findPassenger(int[] now, int count) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(now);
        visited[now[0]][now[1]] = count;
        int nextX; 
        int nextY;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] != o2[0]) return o1[0] - o2[0];
            return o1[1] - o2[1];
        });
        
        int spendFuel = 0;
        while (!queue.isEmpty()) {
            Queue<int[]> nextQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                now = queue.poll();
                
                if (map[now[0]][now[1]] > 1) {
                    pq.add(new int[] {now[0], now[1], map[now[0]][now[1]], spendFuel});
                }

                for (int i = 0; i < 4; i++) {
                    nextX = now[0] + direction[i][0];        
                    nextY = now[1] + direction[i][1];
                    
                    if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N || map[nextX][nextY] == 1 || visited[nextX][nextY] == count) continue;

                    nextQueue.add(new int[] {nextX, nextY});
                    visited[nextX][nextY] = count;
                }
            }
            spendFuel++;
            if (!pq.isEmpty()) {
                return pq.poll();
            }

            queue = nextQueue;
        }

        return new int[] {-1, -1, -1};
    }

    static int[] findDestination(int[] now, int[] destinationPos, int count) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {now[0], now[1], 0});
        int nextX; 
        int nextY;
        while (!queue.isEmpty()) {
            now = queue.poll();
            
            for (int i = 0; i < 4; i++) {
                nextX = now[0] + direction[i][0];        
                nextY = now[1] + direction[i][1];
                
                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N || map[nextX][nextY] == 1 || visited[nextX][nextY] == count) continue;
                
                if (nextX == destinationPos[0] && nextY == destinationPos[1]) {
                    return new int[] {nextX, nextY, now[2]+1};
                }
                queue.add(new int[] {nextX, nextY, now[2]+1});
                visited[nextX][nextY] = count;
            }
        }
  
        return new int[] {-1, -1, -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());
        int M = Integer.parseInt(st.nextToken());
        fuel = Integer.parseInt(st.nextToken());

        // 지도 입력 
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 출발지 목적지
        st = new StringTokenizer(br.readLine());
        int startX = Integer.parseInt(st.nextToken());
        int startY = Integer.parseInt(st.nextToken());
        
        // 승객의 출발지와 목적지
        int passX; int passY; int destX; int destY;
        int[][] destinationList = new int[M+2][2];
        for (int i = 2; i <= M+1; i++) {
            st = new StringTokenizer(br.readLine());
            passX = Integer.parseInt(st.nextToken());
            passY = Integer.parseInt(st.nextToken());
            destX = Integer.parseInt(st.nextToken());
            destY = Integer.parseInt(st.nextToken());
            map[passX-1][passY-1] = i;
            destinationList[i] = new int[] {destX-1, destY-1};
        }

        visited = new int[N][N];
        int count = 1;
        int[] passengerPos;
        int[] destinationPos = new int[] {startX-1, startY-1};
        while (true) {
            
            passengerPos = findPassenger(new int[] {destinationPos[0], destinationPos[1]}, count);
            if ((passengerPos[0] == -1 && passengerPos[1] == -1) || (fuel < passengerPos[3])) {
                fuel = -1;
                break;
            }

            fuel -= passengerPos[3];
            map[passengerPos[0]][passengerPos[1]] = 0;
            count++;

            destinationPos = findDestination(new int[] {passengerPos[0], passengerPos[1]}, destinationList[passengerPos[2]], count);
            if ((destinationPos[0] == -1 && destinationPos[1] == -1) || (fuel < destinationPos[2])) {
                fuel = -1;
                break;
            }

            fuel += destinationPos[2];
            count++;

            M--;
            if (M == 0) {
                break;
            }
        }

        System.out.println(fuel);
    }
}