[ 알고리즘 ] 코딩 - 19238 - 스타트택시.java

---

문제 링크

www.acmicpc.net/problem/19238

19238번: 스타트 택시

---

문제 개요

BOJ 19238 - (자바) 스타트 택시 - 시뮬레이션 / 구현 / BFS 2개

스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

초기 위치 예시

 

---

로직

BFS를 2번 수행해야한다. 승객을 태울때 1번, 승객을 태우고 목적지로 출발할때 한번. 

Step 00. 승객과 택시의 정보를 저장할 class를 만든다. 지도에 승객의 번호를 저장하고, 승객의 정보는 m+2크기의 배열로 관리한다. 0과 1은 빈곳, 벽이기 때문에 2번부터 시작한다.

Step 01. BFS로 거리가 가장 짧은 승객을 찾는다. 여러 사람이 있을 수 있으므로, 큐에 저장된 size별로 확인하고 가장 왼쪽 위의 승객을 태우도록 하자.

Step 02. BFS로 승객의 목적지로 이동한다. 이동중 에너지를 다 썼다면 다음 큐를 확인해줘야한다. 이때 return false를 해줬었는데, 89%에서 틀렸습니다가 나온다. 왜냐하면 승객을 목적지로 이동시키고 에너지를 다 쓴 경우는 고려할 수 없기 때문이다. continue로 바꿔주면 간단히 해결된다.

Step 03. Step 01 ~ Step 02를 M번 반복하고 남은 에너지를 계산하면 정답.

 

---

코드

/**
 * 
 */
package samsung_test;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_19238_스타트택시 {
	static class Passenger { // 승객 정보
		int src_y, src_x, dest_y, dest_x, distance;

		public Passenger(int src_y, int src_x, int dest_y, int dest_x) {
			this.src_y = src_y;
			this.src_x = src_x;
			this.dest_y = dest_y;
			this.dest_x = dest_x;
		}
	}

	static class Taxi { // 택시 정보
		int y, x, energy, passNo;

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

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

		int N = Integer.parseInt(stt.nextToken());
		int M = Integer.parseInt(stt.nextToken());
		int E = Integer.parseInt(stt.nextToken());

		int[][] map = new int[N+1][N+1];

		for (int i = 1; i <= N; i++) {
			stt = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(stt.nextToken());
			}
		}

		stt = new StringTokenizer(br.readLine());
		int y = Integer.parseInt(stt.nextToken());
		int x = Integer.parseInt(stt.nextToken());
		Taxi taxi = new Taxi(y, x, E);

		// 승객 번호 별 배열 관리
		Passenger[] p_arr = new Passenger[M+2];
		for (int m = 0; m < M; m++) {
			stt = new StringTokenizer(br.readLine());
			int src_y = Integer.parseInt(stt.nextToken());
			int src_x = Integer.parseInt(stt.nextToken());
			int dest_y = Integer.parseInt(stt.nextToken());
			int dest_x = Integer.parseInt(stt.nextToken());
			p_arr[m+2] = new Passenger(src_y, src_x, dest_y, dest_x);
			map[src_y][src_x] = m+2;
		} // input end

		int res = process(map, p_arr, taxi, N, M);
		System.out.println(res);
	}

	private static int process(int[][] map, Passenger[] p_arr, Taxi taxi, int n, int m) {
		for (int i = 0; i < m; i++) { // 총 승객 수만큼 반복
			// 거리가 가장 짧은 승객으로 BFS.
			// 택시 승객에게 이동
			if(bfs_to_passenger(map, p_arr, taxi, n)) {
				// 승객 목적지 이동
				if (bfs(map, p_arr, taxi, n)) {
				} else { // 승객 목적지 이동 불가
					return -1;
				}
			} else { // 택시 승객에게 이동 불가
				return -1;
			}
		}
		return taxi.energy;
	}

	// 태울 승객을 가려내자
	private static boolean bfs_to_passenger(int[][] map, Passenger[] p_arr, Taxi taxi, int n) {
		int[] dy = { -1, 1, 0, 0 }; // 상 하 좌 우
		int[] dx = { 0, 0, -1, 1 };
		boolean[][] visited = new boolean[n+1][n+1];
		Queue<int[]> queue = new LinkedList<int[]>();
		// 현재 택시 위치
		queue.offer(new int[] {taxi.y, taxi.x, taxi.energy});
		visited[taxi.y][taxi.x] = true;
		
		while(!queue.isEmpty()) {
			int size = queue.size();
			// 가장 가까운 승객의 위치 정보
			int min_y = n+1;
			int min_x = n+1;
			boolean flag = false;
			// 같은 거리의 승객이 여러명 있을 수 있으므로 사이즈 별로 반복
			for(int s = 0; s < size; s++) {
				int[] pos = queue.poll();
				int y = pos[0];
				int x = pos[1];
				int energy = pos[2];

				// 승객 발견. 규칙에 따라 태울 승객을 가리자
				if (map[y][x] > 1) {
					if(min_y > y) {
						min_y = y;
						min_x = x;
					} else if(min_y == y) {
						if(min_x > x) {
							min_y = y;
							min_x = x;
						}
					}
					flag = true;
					// 에너지 소모는 같으므로 여기서 할당
					taxi.energy = energy;
					continue;
				}

				// 에너지 다 씀
				if (energy <= 0)
					return false;

				// 4방 탐색
				for (int d = 0; d < 4; d++) {
					int next_y = y + dy[d];
					int next_x = x + dx[d];

					if (rangeCheck(next_y, next_x, n) || visited[next_y][next_x] ||
						map[next_y][next_x] == 1)
						continue;
					queue.offer(new int[] { next_y, next_x, energy - 1 });
					visited[next_y][next_x] = true;
				}
			} // 큐 사이즈 순회 end
			// 태울 승객이 있는 경우
			if(flag) {
				taxi.y = min_y;
				taxi.x = min_x;
				taxi.passNo = map[min_y][min_x];
				map[min_y][min_x] = 0;
				return true;
			}
		} // while end
		return false;
	}

	// 승객의 목적지로 이동하자
	private static boolean bfs(int[][] map, Passenger[] p_arr, Taxi taxi, int n) {
		int[] dy = { -1, 1, 0, 0 };
		int[] dx = { 0, 0, -1, 1 };
		boolean[][] visited = new boolean[n+1][n+1];
		Queue<int[]> queue = new LinkedList<int[]>();
		Passenger cur_p = p_arr[taxi.passNo];
		
		queue.offer(new int[] {taxi.y, taxi.x, taxi.energy });
		visited[taxi.y][taxi.x] = true;

		while (!queue.isEmpty()) {
			int size = queue.size();
			int[] pos = queue.poll();
			int y = pos[0];
			int x = pos[1];
			int energy = pos[2];

			// 도착
			if (y == cur_p.dest_y && x == cur_p.dest_x) {
				// 원래 에너지 - 현재 에너지 -> 소모한 에너지
				taxi.y = y;
				taxi.x = x;
				taxi.energy = energy + 2 * (taxi.energy - energy);
				return true;
			}

			// 에너지 다 씀
			if (energy <= 0)
				continue;

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

				if (rangeCheck(next_y, next_x, n) || visited[next_y][next_x] ||
					map[next_y][next_x] == 1)
					continue;
				queue.offer(new int[] { next_y, next_x, energy - 1 });
				visited[next_y][next_x] = true;
			}
		}
		// 도착할 수 없는 경우
		return false;
	}

	private static boolean rangeCheck(int next_y, int next_x, int n) {
		return next_y <= 0 || next_y >= n+1 || next_x <= 0 || next_x >= n+1;
	}
}