[백준] 19238번 : 스타트 택시 - 자바(JAVA)

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

19238번: 스타트 택시

 

문제 해석

스타트 택시는 손님을 도착지로 데려다줄 때마다 연료가 충전된다. (연료는 승객을 태워 이동하면서 소모한 연료 양의 2배가 충전된다.)

연료가 바닥나면 그날의 업무는 끝난다. (실패 시 -1 출력)

 

택시 기사 최백준은 M명의 승객을 태우는 것이 목표이다.

 

활동할 영역은 N*N 크기의 격자이다.

각 칸은 비어있거나 벽이 놓여있다.

 

상하좌우 인접 칸으로 이동할 수 있으며 최단경로로 이동하려고 한다.

 

문제 풀이 전 설계

N의 범위는 20이고 M의 범위는 1 <= M^2 <= 400입니다.

승객을 고를 때는 현재 위치에서 가장 가까운 승객으로 이동하므로 BFS를 사용합니다.

주의할 점은 승객을 태워 이동하면서 소모한 연료 양의 2배를 충전하는 것

또한 최단거리가 같으면 행 번호가 작은 승객을 태워야 합니다.

목적지 또는 승객을 태운 경우 bfsQ를 초기화하면서 다시 돌려줍니다.

 

 

문제 풀이하면서

PriorityQueue를 사용하면서 BFS를 했습니다.

 

우선순위를 먼저 설명하겠습니다

1. moveCount 움직인 횟수가 적을수록 우선권을 가집니다. (이것을 설정하지 않으면 y좌표가 작을수록 우선권을 가져 계속 위쪽만 탐색합니다.)

2. y좌표가 작을수록 우선권을 가집니다.

3. x좌표가 작을수록 우선권을 가집니다.

 

이후 주의할 점은 연료관리입니다.

연로가 0이면 return 하는 구문을 사용하였더니 만약에 현재 연료가 1이고  오른쪽에서 승객을 태울 수 있는데 왼쪽을 먼저 들러서 연료가 0이 되고 return 된다면..? 갈 수 있는 길인데 -1이 출력됩니다.

 

따라서 해당 구문을 제거하고 for(k=0; k <4; k++) 반복문 밑에 연료가 0인 경우에는 BFS.add()를 하지 않도록 하였습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_19238_스타트택시 {

	static class Taxi implements Comparable<Taxi> {
		int y;
		int x;
		int fuel;
		int moveCount;
		int passengerNum;
		boolean isTakePassenger;

		public Taxi(int y, int x, int fuel, int moveCount, int passengerNum, boolean isTakePassenger) {
			super();
			this.y = y;
			this.x = x;
			this.fuel = fuel;
			this.moveCount = moveCount;
			this.passengerNum = passengerNum;
			this.isTakePassenger = isTakePassenger;
		}

		@Override
		public String toString() {
			return "Taxi [y=" + y + ", x=" + x + ", fuel=" + fuel + ", moveCount=" + moveCount + ", passengerNum="
					+ passengerNum + ", isTakePassenger=" + isTakePassenger + "]";
		}

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

	}

	static class Passenger {
		int startY;
		int startX;
		int endY;
		int endX;

		public Passenger(int startY, int startX, int endY, int endX) {
			super();
			this.startY = startY;
			this.startX = startX;
			this.endY = endY;
			this.endX = endX;
		}

	}
	// 상좌우하

	static int N, finishCount, M;
	static int result = -1;
	static Taxi taxi;
	static Passenger[] passengers;
	static boolean[][] visited;
	static int[][] board;

	// bfs

	// 상 좌 우 하
	static int[] dy = { -1, 0, 0, 1 };
	static int[] dx = { 0, -1, 1, 0 };
	// static int[] dy = { -1, 1, 0, 0 };
	// static int[] dx = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int fuel = Integer.parseInt(st.nextToken());

		board = new int[N + 1][N + 1];
		visited = new boolean[N + 1][N + 1];

		for (int y = 1; y <= N; y++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int x = 1; x <= N; x++) {
				board[y][x] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(br.readLine(), " ");
		int startY = Integer.parseInt(st.nextToken());
		int startX = Integer.parseInt(st.nextToken());

		taxi = new Taxi(startY, startX, fuel, 0, 0, false);
		// taxi = new Taxi(y, x, fuel, moveCount, passengerNum, isTakePassenger)

		passengers = new Passenger[M + 2];
		// 1은 벽이다.
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			startY = Integer.parseInt(st.nextToken());
			startX = Integer.parseInt(st.nextToken());
			int endY = Integer.parseInt(st.nextToken());
			int endX = Integer.parseInt(st.nextToken());

			board[startY][startX] = i + 2;
			// board[endY][endX] = i+2;

			// 헷갈려서 그냥 손님2부터시작
			passengers[i + 2] = new Passenger(startY, startX, endY, endX);

		}

		/*
		for (int i = 2; i < M + 2; i++) {
			System.out.println(passengers[i].endY + " " + passengers[i].endX);
		}
		for (int y = 1; y <= N; y++) {
			for (int x = 1; x <= N; x++) {
				System.out.print(board[y][x] + " ");
			}
			System.out.println();
		}
		 */
		
		startTaxi();

		System.out.println(result);
	}

	private static void startTaxi() {
		PriorityQueue<Taxi> bfsQ = new PriorityQueue<Taxi>();
		// Queue<Taxi> bfsQ = new LinkedList<Taxi>();

		bfsQ.add(taxi);
		visited[taxi.y][taxi.x] = true;

		outer: while (!bfsQ.isEmpty()) {

			Taxi currentTaxi = bfsQ.poll();

			// 손님을 태운상황
			if (currentTaxi.isTakePassenger) {
				// 원하는 목적지 도착?
				if (currentTaxi.y == passengers[currentTaxi.passengerNum].endY
						&& currentTaxi.x == passengers[currentTaxi.passengerNum].endX) {
										
					bfsQ.clear();
					visited = new boolean[N + 1][N + 1];
					finishCount++;
					currentTaxi.fuel += currentTaxi.moveCount * 2;
					bfsQ.add(new Taxi(currentTaxi.y, currentTaxi.x, currentTaxi.fuel, 0, 0, false));
					visited[currentTaxi.y][currentTaxi.x] = true;

					// 모든 손님들이 목적지에 도착했다면?
					if (finishCount == M) {
						// 끝
						result = currentTaxi.fuel;

						return;
					}
					continue outer;
				}
			}

			// 손님을 태우지 않은 상황
			if (!currentTaxi.isTakePassenger) {
				// 해당칸이 손님을 태울 수 있다면
				if (board[currentTaxi.y][currentTaxi.x] > 1) {
					
					bfsQ.clear();
					visited = new boolean[N + 1][N + 1];

					currentTaxi.isTakePassenger = true;
					currentTaxi.passengerNum = board[currentTaxi.y][currentTaxi.x];
					board[currentTaxi.y][currentTaxi.x] = 0;

					bfsQ.add(new Taxi(currentTaxi.y, currentTaxi.x, currentTaxi.fuel, 0, currentTaxi.passengerNum,
							true));
					continue outer;
				}
			}

			for (int k = 0; k < 4; k++) {

				if (currentTaxi.fuel == 0) {
					continue;
				}

				int tempY = currentTaxi.y + dy[k];
				int tempX = currentTaxi.x + dx[k];

				// 좌표가 유효하지 않거나 || 이미 방문했거나 || 벽으로 막혀있거나
				if (tempY < 1 || tempX < 1 || tempY >= N + 1 || tempX >= N + 1 || visited[tempY][tempX]
						|| board[tempY][tempX] == 1) {
					continue;
				}

				visited[tempY][tempX] = true;
				bfsQ.add(new Taxi(tempY, tempX, currentTaxi.fuel - 1, currentTaxi.moveCount + 1,
						currentTaxi.passengerNum, currentTaxi.isTakePassenger));

			}
		}

	}

}