[백준] 19238. 스타트 택시

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

19238번: 스타트 택시

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

		public Passenger(int sx, int sy, int ex, int ey) {
			this.sx = sx;
			this.sy = sy;
			this.ex = ex;
			this.ey = ey;
		}
	}

	static class Pair {
		int x;
		int y;

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

	static int N, M, fuel, tx, ty, add;
	static int[][] map, dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static Queue<Pair> queue;
	static boolean[][] visited;
	static Passenger[] passengers;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		fuel = Integer.parseInt(st.nextToken());

		map = new int[N + 1][N + 1];
		passengers = new Passenger[M + 1];

		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j < N + 1; j++) {
				int val = Integer.parseInt(st.nextToken());
				if (val == 1) {
					map[i][j] = -1;
				} else {
					map[i][j] = val;
				}

			}
		}

		st = new StringTokenizer(br.readLine(), " ");
		tx = Integer.parseInt(st.nextToken());
		ty = Integer.parseInt(st.nextToken());

		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());

			map[sx][sy] = i;
			passengers[i] = new Passenger(sx, sy, ex, ey);
		}


		int sum = 0;

		while (true) {

			// 1. 택시의 출발 위치에서 가장 가까운 손님을 찾고 손님의 번호를 리턴. 그런 승객이 여러명이면
			// 그 중 행 번호가 가장 작은 승객 -> 열번호가 가장 작은 승객

			List<Pair> list = findCustomer(tx, ty);

			if (list.size() == 0) {
				System.out.println(-1);
				return;
			} else {
				Collections.sort(list, new Comparator<Pair>() {
					public int compare(Pair o1, Pair o2) {
						if (o1.x < o2.x)
							return -1;
						else if (o1.x == o2.x) {
							if (o1.y < o2.y)
								return -1;
						}
						return 1;
					}
				});
			}

			int num = map[list.get(0).x][list.get(0).y];
			map[list.get(0).x][list.get(0).y] = 0;
			tx = list.get(0).x;
			ty = list.get(0).y;

			

			add = 0;

			// 2. 손님 번호의 목적지 까지 이동한다.
			if (!findDestination(tx, ty, passengers[num].ex, passengers[num].ey)) {
				System.out.println(-1);
				return;
			}


			sum++;
			if (sum == M) {
				System.out.println(fuel);
				break;
			}

		}
	}

	public static boolean findDestination(int x, int y, int ex, int ey) {

		queue = new LinkedList();
		visited = new boolean[N + 1][N + 1];

		queue.offer(new Pair(x, y));
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int len = queue.size();
			fuel--;
			add++;
			for (int l = 0; l < len; l++) {
				Pair p = queue.poll();

				for (int i = 0; i < 4; i++) {
					int nx = p.x + dir[i][0];
					int ny = p.y + dir[i][1];

					if (isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] != -1) {
						if (nx == ex && ny == ey) { // 현재 태운 승객의 목적지 칸
							tx = nx;
							ty = ny;
							fuel += add * 2;
							return true;
						} else {
							queue.offer(new Pair(nx, ny));
							visited[nx][ny] = true;
						}
					}
				}
			}

			if (fuel == 0)
				return false;
		}

		return false;
	}

	public static ArrayList findCustomer(int x, int y) {

		ArrayList<Pair> list = new ArrayList();

		if (map[x][y] >= 1) {
			list.add(new Pair(x, y));
			return list;
		}

		queue = new LinkedList();
		visited = new boolean[N + 1][N + 1];

		queue.offer(new Pair(x, y));
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int len = queue.size();
			fuel--;

			boolean flag = false;

			for (int l = 0; l < len; l++) {
				Pair p = queue.poll();
				for (int i = 0; i < 4; i++) {
					int nx = p.x + dir[i][0];
					int ny = p.y + dir[i][1];

					if (isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] != -1) {
						if (map[nx][ny] == 0) { // 빈칸
							queue.offer(new Pair(nx, ny));
							visited[nx][ny] = true;
						} else if (map[nx][ny] >= 1) { // 승객이 있는 칸
							visited[nx][ny] = true;
							list.add(new Pair(nx, ny));
							flag = true;
						}
					}
				}
			}

			if (flag)
				return list;

			if (fuel == 0)
				return new ArrayList();
		}

		return new ArrayList();
	}


	public static boolean isInside(int x, int y) {
		return x >= 1 && x <= N && y >= 1 && y <= N;
	}
}