백준 : 19238 스타트 택시 (JAVA)

www.acmicpc.net/problem/19238

19238번: 스타트 택시

package test;

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

public class B19238 {
	static int N, M;
	static int[][] map;
	static int[][] sMap;
	static int[][] eMap;

	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());
		int E = Integer.parseInt(st.nextToken());

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

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

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

			/*
			 * 출발 승객 위치
			 */
			sMap[sy][sx] = m;

			/*
			 * 내리는 승객 위치
			 */
			eMap[m][0] = ey;
			eMap[m][1] = ex;
		}

		System.out.println(Solve(ty, tx, E));

	}

	private static int Solve(int ty, int tx, int e) {
		int entCnt = 0;
//		System.out.println(ty + " " + tx);
		while (entCnt != M) {
			/*
			 * ty ,tx에서 가장 거리가 짧은 승객 구하기
			 */
			int res[] = getShortConsumer(ty, tx);
			/*
			 * e < 이동거리 음수면 -1
			 */
			if (res[0] == 0)
				return -1;

			if (e < res[1])
				return -1;
			e -= res[1];
			ty = res[2];
			tx = res[3];

//			System.out.println(ty + " " + tx);

			int takeOutDistance = getTakeOutDistance(ty, tx, res[0]);
			/*
			 * e < 하차거리 -1
			 */
			if (takeOutDistance == -1)
				return -1;
			if (e < takeOutDistance)
				return -1;
			ty = eMap[res[0]][0];
			tx = eMap[res[0]][1];
//			System.out.println(ty + " " + tx);

			/*
			 * e = e + 하차거리*2;
			 */
			e += takeOutDistance;
			entCnt++;
		}
		return e;
	}

	static int dy[] = { 1, -1, 0, 0 };
	static int dx[] = { 0, 0, 1, -1 };
	static boolean check[][];

	static class Pair {
		int y;
		int x;

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

	private static int[] getShortConsumer(int ty, int tx) {
		Queue<Pair> q = new LinkedList<Pair>();
		check = new boolean[N + 1][N + 1];
		check[ty][tx] = true;
		q.add(new Pair(ty, tx));
		/*
		 * res[0] : 승객번호 res[1] : 거리
		 */
		int res[] = new int[4];
		int time = 0;
		int tmpY = 0;
		int tmpX = 0;
		boolean success = false;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int s = 0; s < size; s++) {
				Pair cur = q.poll();
				if (sMap[cur.y][cur.x] != 0) {
					if (!success) {
						success = true;
						tmpY = cur.y;
						tmpX = cur.x;
						res[0] = sMap[cur.y][cur.x];
					} else {
						if (tmpY > cur.y) {
							tmpY = cur.y;
							tmpX = cur.x;
							res[0] = sMap[cur.y][cur.x];
						} else if (tmpY == cur.y) {
							if (tmpX > cur.x) {
								tmpX = cur.x;
								res[0] = sMap[cur.y][cur.x];
							}
						}
					}
				}
				/*
				 * 4방향 탐색
				 */
				for (int d = 0; d < 4; d++) {
					int ny = dy[d] + cur.y;
					int nx = dx[d] + cur.x;
					if (ny < 1 || nx < 1 || ny > N || nx > N)
						continue;
					if (check[ny][nx])
						continue;
					if (map[ny][nx] == 1)
						continue;
					check[ny][nx] = true;
					q.add(new Pair(ny, nx));

				}

			}

			if (success) {
				res[1] = time;
				res[2] = tmpY;
				res[3] = tmpX;
				sMap[tmpY][tmpX] = 0;
				break;
			}

			time++;

		}

		return res;
	}

	private static int getTakeOutDistance(int y, int x, int end) {
		check = new boolean[N + 1][N + 1];
		Queue<Pair> q = new LinkedList<Pair>();
		int ey = eMap[end][0];
		int ex = eMap[end][1];

		check[y][x] = true;
		q.add(new Pair(y, x));
		int time = 0;

		while (!q.isEmpty()) {
			int size = q.size();
			for (int s = 0; s < size; s++) {
				Pair cur = q.poll();
				if (cur.y == ey && cur.x == ex) {
					return time;
				}

				for (int d = 0; d < 4; d++) {
					int ny = dy[d] + cur.y;
					int nx = dx[d] + cur.x;
					if (ny < 1 || nx < 1 || ny > N || nx > N)
						continue;
					if (check[ny][nx])
						continue;
					if (map[ny][nx] == 1)
						continue;
					check[ny][nx] = true;
					q.add(new Pair(ny, nx));
				}
			}
			time++;
		}
		return -1;
	}
}

 

그냥 시키는 데로 구현 하면 된다. 문제에 나와있지 않은 설명은

1. 택시가 승객을 태우로 못갈경우 -1
2. 택시가 승객을 하차하로 못갈경우 -1

위에 두가지 경우 더추가하고 짜면됨