[backjoon]19238 스타트택시 java

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

19238번: 스타트 택시

이 문제는 세세한 사항이 많아서 정밀하게 하지 않으면 통과하기 어렵다고 생각한다.

큰 틀만 보면 BFS를 2번 돌리는데, 거리도 표시해주어야한다.

1. 현재 위치에서 최단 거리 승객을 찾기위한 BFS
2.  승객을 목적지까지 최단 거리로 데려다주기 위한 BFS

1. 에서 승객을 찾을 때 가장 가까운 승객, 가까운 승객이 많다면 행이 작은 순서, 열이 작은 순서대로 찾는다.

이 점을 간과하였는데, 북, 동, 서, 남 순으로 구현해야지 했다가는 처음부터 틀렸습니다.를 맞기 쉽상이다.

따라서 정렬을 통해 최단 거리 승객을 찾아야한다.

문제에도 나와있지만 승객은 거리가 0일 수도 있기 때문에, 첫 위치를 꼭 탐색해줘야한다.

2에서는 연료가 소진되거나 승객이 벽에 막혀 못 갈 수 있는 경우도 있기 때문에 이 점 역시 신경써야한다.(나의 경우 거리를 리턴할 때, Integer 의 최소 값을 리턴하도록 하였다.)

추가로 승객의 목적지 맵핑을 나의 경우엔, 

지도 상에 0은 길, 1은 벽임을 이용하여 2부터 승객이라고 간주하고, 위치 정보를 담은 배열을 만들어 해당 인덱스에 맞는 목적지 정보를 가져와서 거리 이동을 해주었다.

이 문제를 해결하기 위해서는 BFS + 정렬을 기반으로 거리 파악을 위한 배열, 목적지 정보를 담기 위한 배열, 연료 관리를 위한 변수등 꼼꼼한 풀이가 필요하다고 생각든다.

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

class Main {
	static boolean[][] marked;
	static int[][] map, distance;
	static int N, M, fuel;
	static int[][] dirs = { { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 } };
	static Dot[] arr;
	static Dot start;
	static boolean possible;

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		fuel = Integer.parseInt(st.nextToken());
		arr = new Dot[M + 2]; // 손님을 파악하기 위한 변수. 2부터 시작하기 때문에 +2를 해줌.
		//벽은 1 길은 0인점을 이용해서 map에 2 이상인 경우에 손님이라고 간주하기로 하였다.
		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int cur = Integer.parseInt(st.nextToken());
				map[i][j] = cur;
			}
		}

		st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		start = new Dot(x, y);

		for (int j = 2; j < M+2; j++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int nextR = Integer.parseInt(st.nextToken());
			int nextC = Integer.parseInt(st.nextToken());
			arr[j] = new Dot(nextR, nextC);
			map[r][c] = j;
		}
		//연료가 없거나 다 찾으면 종료, 또는 도달하지 못해도 종료(flag)
		while (fuel > 0 && M > 0) {
			closeGuest();
			if (!possible)
				break;
		}
		if (M > 0 || fuel < 0)
			fuel = -1;
		System.out.println(fuel);
	}

	public static void closeGuest() {
		possible = false;
		marked = new boolean[N + 1][N + 1];
		Queue<Dot> queue = new LinkedList<>();
		distance = new int[N + 1][N + 1];
		queue.add(start);
		marked[start.row][start.col] = true;

		PriorityQueue<Dot> resultTarget = new PriorityQueue<>();

		//시작점에 승객이 있다면 바로 목적지로 출발.
		if (map[start.row][start.col] > 1) {
			possible = true;
			int nextIdx = map[start.row][start.col];
			Dot target = arr[nextIdx];
			map[start.row][start.col] = 0;
			int curFuel = distance[start.row][start.col];
			fuel += move(start, target, curFuel);
			start = target;
			M--;
			return;
		}
		int minDis = Integer.MAX_VALUE;
		while (!queue.isEmpty()) {
			Dot cur = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nextR = cur.row + dirs[i][0];
				int nextC = cur.col + dirs[i][1];

				if (nextR <= 0 || nextC <= 0 || nextR > N || nextC > N)
					continue;
				if (marked[nextR][nextC])
					continue;
				if (map[nextR][nextC] == 1)
					continue;
				//승객을 모두 불러넣는다. 최단 거리를 기록하여 최단 거리 승객을 고를 수 있도록 함.
				if (map[nextR][nextC] > 1) {
					possible = true;
					marked[nextR][nextC] = true;
					resultTarget.add(new Dot(nextR, nextC));
					distance[nextR][nextC] = distance[cur.row][cur.col] + 1;
					minDis = Math.min(minDis, distance[nextR][nextC]);
					continue;
				}
				queue.add(new Dot(nextR, nextC));
				marked[nextR][nextC] = true;
				distance[nextR][nextC] = distance[cur.row][cur.col] + 1;
			}
		}
		
		if (resultTarget.isEmpty()) return;
		
		//승객이 있는 경우.
		Dot curStart = resultTarget.poll();
		while (true) {
			if (minDis == distance[curStart.row][curStart.col])
				break;
			curStart = resultTarget.poll();
		}
		int nextIdx = map[curStart.row][curStart.col];
		Dot target = arr[nextIdx];
		map[curStart.row][curStart.col] = 0;
		int curFuel = distance[curStart.row][curStart.col];

		fuel += move(curStart, target, curFuel);
		start = target;
		M--;

	}

	public static int move(Dot start, Dot target, int curFuel) {
		marked = new boolean[N + 1][N + 1];
		distance = new int[N + 1][N + 1];
		Queue<Dot> queue = new LinkedList<>();
		queue.add(start);
		while (!queue.isEmpty()) {
			Dot cur = queue.poll();

			for (int i = 0; i < 4; i++) {
				int nextR = cur.row + dirs[i][0];
				int nextC = cur.col + dirs[i][1];

				if (nextR <= 0 || nextC <= 0 || nextR > N || nextC > N)
					continue;

				//목적지에 도착.
				if (nextR == target.row && nextC == target.col) {
					int curDis = distance[cur.row][cur.col] + 1;
					if (fuel - curDis < 0) // 이동 중 연료가 바닥나는 경우
						return Integer.MIN_VALUE;
					if (fuel - curDis - curFuel < 0) // 승객을 데려다 주는 과정에서 연료가 바닥나는 경우.
						return Integer.MIN_VALUE;
					return curDis - curFuel;
				}
				
				if (marked[nextR][nextC])
					continue;
				if (map[nextR][nextC] == 1)
					continue;

				marked[nextR][nextC] = true;
				queue.add(new Dot(nextR, nextC));
				distance[nextR][nextC] = distance[cur.row][cur.col] + 1;
			}
		}

		return Integer.MIN_VALUE;
	}
}

class Dot implements Comparable<Dot> {
	int row;
	int col;

	Dot(int r, int c) {
		row = r;
		col = c;
	}

	@Override
	public int compareTo(Dot o) {
		// TODO Auto-generated method stub
		if (this.row == o.row)
			return this.col - o.col;
		return this.row - o.row;
	}
}