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

Problem

• 문제 링크

모든 승객들을 도착지에 옮겨주고 난 뒤 남은 연료의 양을 출력하는 문제입니다.

승객들을 데리러 가는 기준은 가까운 기준이며 같은 거리에 여러 명의 승객이 있다면 행 번호가 가장 작고 열 번호가 가장 작은 승객을 데리러 갑니다.

Solution

귀찮은 구현 문제입니다.

아래 과정을 계속 반복하면 됩니다.

1. BFS 를 사용하여 승객 찾기
2. 가장 가까운 승객 비교
3. 도착지에 데려다줌
4. 연료 확인

주의사항도 있습니다.

1. A 의 도착지와 B 의 출발지가 같은 경우 존재 -> 택시의 현재 위치도 검사
2. 도착지는 겹칠 수 있음 -> 도착지를 특정해놓고 BFS 를 진행
3. 행과 열 우선순위 헷갈리지 않게 주의
4. 연료는 많은데 벽에 막혀서 출발지 또는 도착지로 가지 못하는 경우 -> 승객을 태우거나 내리지 못했는데 BFS 가 끝나진 않았는지 확인

변수

변수	설명
Taxi Class	택시 클래스입니다. BFS 에서 좌표를 담아두기 위해 사용하며 택시가 이동한 거리인 move 변수를 갖고 있습니다.
Passenger Class	승객 클래스입니다. 승객의 아이디, 출발지와 도착지 좌표를 갖고 있습니다. 아이디는 2 부터 시작합니다.
taken	현재 타고 있는 승객입니다. null 이면 아무도 타지 않은 상태, 누군가 타고 있다면 해당 승객 객체가 들어갑니다.
passMap	승객 리스트입니다. 승객이 도착지에 내릴 때마다 해당 승객을 지워가면서 모든 승객이 내렸는지 체크합니다.
candidates	택시로부터 같은 거리에 있는 승객들입니다. 택시에 탈 수 있는 후보들이며 행과 열을 비교하기 위해 사용합니다.

가장 가까운 승객 비교하기

Taxi 클래스에 있는 move 변수를 이용하면 특정 좌표에 도달했을때 택시 위치로부터 얼만큼 이동했는지 알 수 있습니다.

BFS 를 진행하면서 승객 위치에 도달하면 candidates 큐에 담아둡니다.

prevMove 변수를 사용해서 이전 move 를 기억하고 있다가 둘이 달라지는 순간에 candidates 큐에 값이 있는지 없는지 검사합니다.

만약 값이 없으면 계속 BFS 를 진행하면 되고 값이 있다면 최단거리인 승객들을 이미 찾았기 때문에 break 로 빠져나옵니다.

candidates 큐에 있는 승객들은 모두 거리가 같기 때문에 행과 열을 비교하여 조건에 맞는 승객을 찾아서 태웁니다.

우선순위 큐를 쓰면 큐에 넣을때마다 매번 비교를 하기 때문에 그냥 일반큐로 하고 나중에 비교했습니다.

도착지에 데려다줌

taken 으로 타고 있는 승객의 정보를 알 기 때문에 도착지 좌표에 도달할 때까지 BFS 를 진행하면 됩니다.

연료 확인

BFS 가 끝나면 prevMove 값을 반환합니다.

이동한 거리, 즉 사용한 연료기 때문에 전체 연료량과 연산한 뒤 음수가 되는지 확인하면 됩니다.

벽에 막혀서 연료가 충분한데 도달할 수 없거나 이동 중에 연료가 떨어지면 Integer.MAX_VALUE 를 리턴하여 fuel 값을 음수로 만들어줍니다.

Java Code

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

class Main {
    static class Taxi {
        int x, y, move;

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

    static class Passenger {
        int id, sx, sy, ex, ey;

        Passenger() { }
    }

    static int N, M, fuel;
    static int[][] arr = new int[21][21];
    static Taxi taxi;
    static Passenger taken = null;
    static Map<Integer, Passenger> passMap = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        fuel = Integer.parseInt(st.nextToken());

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j < N + 1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        taxi = new Taxi(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            Passenger p = new Passenger();
            p.id =  i + 2;  // 벽이 1 이라서 2 부터 넘버링
            p.sx = Integer.parseInt(st.nextToken());
            p.sy = Integer.parseInt(st.nextToken());
            p.ex = Integer.parseInt(st.nextToken());
            p.ey = Integer.parseInt(st.nextToken());

            passMap.put(p.id, p);

            // 출발지는 겹치지 않기 때문에 맵에 기록
            arr[p.sx][p.sy] = p.id;
        }

        // solution
        solution();
    }

    // 모든 승객을 데려다 줄때까지 BFS 를 반복하며 연료의 양을 확인한다.
    static void solution() {
        while (!passMap.isEmpty()) {
            int toStartFuel = bfs();
            fuel -= toStartFuel;

            if (fuel < 0) break;

            int toDestFuel = bfs();
            fuel -= toDestFuel;

            if (fuel < 0) break;

            fuel += toDestFuel * 2;
        }

        System.out.println(fuel < 0 ? -1 : fuel);
    }

    static int bfs() {
        Queue<Taxi> q = new LinkedList<>();
        Queue<Passenger> candidates = new LinkedList<>();
        boolean[][] visited = new boolean[21][21];
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        int prevMove = taxi.move;
        visited[taxi.x][taxi.y] = true;
        q.add(taxi);

        while (!q.isEmpty()) {
            Taxi now = q.poll();

            // 이동 중에 연료가 떨어지면 종료
            if (fuel - now.move < 0) {
                return Integer.MAX_VALUE;
            }

            // 택시 이동 시간대가 다르고 candidates 가 이미 존재하면 break
            if (prevMove != now.move && !candidates.isEmpty()) {
                break;
            }

            prevMove = now.move;

            if (taken == null) {
                // 택시가 비어있는 경우 가장 가까운 승객 후보를 만나면 candidates 에 추가
                int id = arr[now.x][now.y];

                if (id > 1) {
                    Passenger p = passMap.get(id);
                    candidates.add(p);
                }
            } else {
                // 택시에 승객이 있는 경우 도착지를 만나면 종료
                if (now.x == taken.ex && now.y == taken.ey) {
                    passMap.remove(taken.id);
                    taken = null;
                    taxi = new Taxi(now.x, now.y, 0);
                    return prevMove;
                }
            }

            // 동서남북 이동
            for (int i = 0 ; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (0 < nx && nx < N+1 && 0 < ny && ny < N+1) {
                   if (arr[nx][ny] != 1 && visited[nx][ny] == false) {
                       q.add(new Taxi(nx, ny, now.move + 1));
                       visited[nx][ny] = true;
                   } 
                }
            }
        }

        // while 문이 끝났는데 candidates 에 아무것도 없으면 벽에 막혀서 도달못함
        if (candidates.isEmpty()) {
            return Integer.MAX_VALUE;
        }

        taken = findNearest(candidates);
        taxi = new Taxi(taken.sx, taken.sy, 0);
        arr[taken.sx][taken.sy] = 0;
        return prevMove;
    }

    // 같은 거리면 x 가 작고, y 가 작은 사람으로
    static Passenger findNearest(Queue<Passenger> q) {
        Passenger target = q.poll();

        while (!q.isEmpty()) {
            Passenger compare = q.poll();

            if (compare.sx < target.sx) {
                target = compare;
            } else if (compare.sx == target.sx && compare.sy < target.sy) {
                target = compare;
            }
        }

        return target;
    }
}