[Baekjoon] 19238_스타트 택시

Gold II

문제(출처: https://www.acmicpc.net/problem/19238)

---

< 스타트 택시 >

 

문제 풀이 

 

현재 위치에서 모든 위치를 탐색하여 가장 가까이 있는 손님을 찾는다. 손님 위치로 이동 후 손님의 목적지까지 이동한다. 이 과정을 모든 손님을 이동시킬 때까지 반복한다.

 

이 문제에서 고려해야 할 것은 최단 거리가 같은 손님이 있다면 행 번호가 작고, 열 번호가 작은 손님을 택해야 하는 것이다. 

 

 my solution (Java)

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

public class _19238_ { // 스타트 택시
	static int arr[][], n;
	static boolean visited[][];
	static int dx[] = { -1, 0, 0, 1 }; // 상좌우하
	static int dy[] = { 0, -1, 1, 0 };

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

		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int fuel = Integer.parseInt(st.nextToken());

		arr = new int[n + 1][n + 1];
		visited = new boolean[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 1; j <= n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(bf.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());

		int idx = 2;
		HashMap<Integer, int[]> map = new HashMap<>();

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int startX = Integer.parseInt(st.nextToken());
			int startY = Integer.parseInt(st.nextToken());
			int endX = Integer.parseInt(st.nextToken());
			int endY = Integer.parseInt(st.nextToken());

			arr[startX][startY] = idx;
			map.put(idx++, new int[] { endX, endY });
		}

		while (fuel > 0) {
			init();
			int info[] = findCustomer(x, y);

			if (info[0] == -1 && info[1] == -1) {
				break;
			}

			arr[info[0]][info[1]] = 0;
			fuel -= info[3];
			if (fuel <= 0) {
				break;
			}

			init();
			info = taxi(info[0], info[1], map.get(info[2]));

			if (info[0] == -1 && info[1] == -1) {
				break;
			}

			fuel -= info[2];
			if (fuel < 0) {
				break;
			}
			fuel += (info[2] * 2);
			m -= 1;
			x = info[0];
			y = info[1];

			if (m == 0) {
				break;
			}

		}

		if (m > 0 || fuel <= 0) { // 모든 손님을 이동시킬 수 없거나 이동 도중에 연료가 바닥난 경우
			System.out.println(-1);
		} else { // 모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양
			System.out.println(fuel);
		}

	}

	// 방문 배열 초기화
	private static void init() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				visited[i][j] = false;
			}
		}

	}

	// 현재 위치에서 가장 가까운 손님 찾기
	private static int[] findCustomer(int x, int y) {
		if (arr[x][y] > 1) {
			return new int[] { x, y, arr[x][y], 0 };
		}

		Queue<int[]> queue = new LinkedList<>();
		PriorityQueue<int[]> pri = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[3] == o2[3]) {
					if (o1[0] == o2[0]) {
						return o1[1] - o2[1];
					}
					return o1[0] - o2[0];
				}
				return o1[3] - o2[3];
			}
		});
		queue.add(new int[] { x, y, 0 });
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int info[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int a = info[0] + dx[i];
				int b = info[1] + dy[i];
				if (a > 0 && a <= n && b > 0 && b <= n && arr[a][b] != 1 && !visited[a][b]) {
					visited[a][b] = true;
					if (arr[a][b] > 1) {
						if (pri.size() == 0 || pri.peek()[3] >= info[2] + 1) {
							pri.add(new int[] { a, b, arr[a][b], info[2] + 1 });
						}
					}
					queue.add(new int[] { a, b, info[2] + 1 });
				}
			}
		}

		if (pri.isEmpty()) {
			return new int[] { -1, -1, -1, -1 };
		} else {
			return pri.poll();
		}
	}

	// 손님 출발지에서 목적지까지 이동
	private static int[] taxi(int x, int y, int[] find) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y, 0 });
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int info[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int a = info[0] + dx[i];
				int b = info[1] + dy[i];
				if (a > 0 && a <= n && b > 0 && b <= n && arr[a][b] != 1 && !visited[a][b]) {
					visited[a][b] = true;
					if (a == find[0] && b == find[1]) {
						return new int[] { a, b, info[2] + 1 };
					}
					queue.add(new int[] { a, b, info[2] + 1 });
				}
			}
		}
		return new int[] { -1, -1, -1 };
	}
}

변수)
n : 격자 크기
m : 손님 수
fuel : 연료 양
arr : 지도 정보
visited : 방문 여부
x, y : 운전을 시작하는 칸의 행 번호, 열 번호 
idx : 손님 번호
map : <손님 번호, 손님 목적지>
startX, startY, endX, endY : 손님의 출발지의 행, 열 번호, 목적지의 행, 열 번호

 

Main

격자 크기, 손님 수, 연료 양을 입력받는다. 지도 정보를 입력받아 arr에 저장한다. 운전을 시작하는 위치를 입력받고, 손님의 위치를 입력받는다. 손님의 위치를 입력받아 arr 지도에 손님 번호를 저장하고, HashMap에 손님 번호와 목적지 위치를 저장한다.

 

연료가 남아있는 동안 아래 과정을 반복한다.

1) 방문 배열 초기화

2) findCustomer 함수를 통해 현재 위치에서 가장 가까운 손님 위치 구하기

3) 만약 모든 손님한테 이동할 수 없다면 종료

4) 가까운 손님한테 이동 후 연료 소모. 연료가 0 이하라면 목적지까지 이동할 수 없으므로 종료

5) 방문 배열 초기화

6) 손님을 태우고 손님 목적지까지 이동

7) 목적지까지 이동할 수 없다면 종료

8) 목적지까지 이동 후 연료 소모. 만약 남은 연료가 0보다 작다면 목적지까지 이동 불가능한 것이므로 종료. 남은 연료가  0 이상이라면 소모한 연료 양의 두 배 충전

9) 손님 한 명을 목적지까지 이동시킨 것이므로 m-1 및 현재 위치 업데이트

10) m이 0이라면 모든 손님을 목적지까지 이동시킨 것이므로 종료

 

모든 손님을 이동시킬 수 없거나 이동 도중에 연료가 바닥난 경우 -1을 출력한다. 그 외 모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다.

 

init

방문 배열 viisted를 false로 초기화한다.

 

findCustomer (x, y)

: [손님 위치, 손님 번호, 거리] 반환

시작 위치에 손님이 있다면 가장 가까운 손님이므로 값을 반환하고 종료한다.

queue에 [시작 위치, 거리 0]을 저장하며 시작 위치를 방문 표시한다. 

우선순위 큐는 [손님 위치 x, y, 손님 번호, 거리]를 저장하며 거리를 우선순위로, 거리가 같다면 손님 위치의 x, y를 우선순위로 둔다.

 

queue가 빌 때까지 아래 과정을 반복한다.

1) queue poll

2) 상좌우하 탐색하여 지도 범위 안이며 비어있는 칸이며 아직 방문하지 않은 곳이라면 방문 표시한다. 만약 그 위치에 손님이 있다면 우선순위 큐가 비었거나 우선순위 큐에 있는 값의 최단거리보다 작거나 같다면 값을 추가한다. 손님이 있거나 없거나 queue에는 값을 추가한다.

 

우선순위 큐가 비었다면 어느 손님한테도 갈 수 없다는 뜻이므로 -1이 든 배열을 반환한다. 우선순위 큐에 값이 있다면 poll 한 값을 반환한다. 

 

taxi (x, y, 도착위치 find)

: [손님 위치, 거리] 반환

queue에 [시작 위치, 거리 0]을 저장하며 시작 위치를 방문 표시한다.

 

queue가 빌 때까지 아래 과정을 반복한다.

1) queue poll

2) 상좌우하 탐색하여 지도 범위 안이며 비어있는 칸이며 아직 방문하지 않을 곳이라면 방문 표시한다. 만약 그 위치가 도착 위치라면 [도착 위치, 거리]를 반환한다. 도착 위치가 아니라면 queue에 값을 저장한 후 계속한다.

 

만약 도착 위치에 도달하지 못한다면 -1이 든 배열을 반환한다. 

---

---