백준 19238 : 스타트 택시

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

19238번: 스타트 택시

[ 문제풀이 ]

이번에도 역시 지문 내용을 그대로 구현할 수 있으면 정답을 맞힐 수 있는 문제이다. 주어진 지문을 토대로 총 2단계 과정으로 세분화할 수 있다.

1. ​현재 택시 위치에서 가장 가까운 거리에 있는 승객을 찾는다.
2. 현재 탑승한 승객을 목적지까지 데려다준다.

 

​다만, 조심해야 할 부분이 있다. 승객의 출발지는 겹치지 않지만 목적지는 겹칠 수 있다는 것이다.

나는 처음에 목적지도 겹치지 않는다고 생각하여 1차원 배열로 map을 만들어 구현하였지만 목적지가 겹치는 바람에 map에 누적되면서 이전 값이 사라져 문제가 발생하였다.

이를 해결하기 위해 승객의 수 M 만큼 goal이라는 map을 만들어 각각 저장하였다.

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

public class Main {

	static int N, M, f;
	static int[][] start;
	static int[][][] goal;
	static Taxi taxi;
	static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
	
	static class Taxi {
		int idx, y, x, fuel;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		f = Integer.parseInt(st.nextToken());
		start = new int[N+1][N+1];
		//승객의 출발지는 다르지만 목적지는 같을 수 있기 때문에
        //배열 한곳에 저장하게 되면 누적되면서 사라짐
		//이를 해결하기 위해 승객의 수만큼 배열을 만듬
		goal = new int[M+1][N+1][N+1];

		for (int i = 1; i <= N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; ++j) {
				int block = Integer.parseInt(st.nextToken());
				// 편하게 구현하기 위해 벽을 1대신 -1로 받음
				start[i][j] = block == 1 ? -1 : 0;
				for (int k = 1; k <= M; ++k) {
					goal[k][i][j] = start[i][j];
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		taxi = new Taxi(-10, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), f);
		for (int i = 1; i <= M; ++i) {
			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());
			start[sy][sx] = i;
			goal[i][ey][ex] = i;
		}

		boolean flag = true;
		while (M > 0) {
			//1. 현재 택시 위치에서 가장 가까운 거리에 있는 승객을 찾는다.
			findToClient();

			if (taxi == null) {
				flag = false;
				bw.write(-1 + "\n");
				break;
			}

			//2. 현재 탑승한 승객을 목적지까지 데려다 준다.
			findToDestination();
			if (taxi == null) {
				flag = false;
				bw.write(-1 + "\n");
				break;
			}
			M--;
		}
		if (flag) bw.write(taxi.fuel + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void findToClient() {
		Queue<Taxi> q = new LinkedList<>();
		boolean[][] visit = new boolean[N+1][N+1];
		boolean client_find = false;

		visit[taxi.y][taxi.x] = true;
		q.offer(new Taxi(taxi.idx, taxi.y, taxi.x, taxi.fuel));

		while (!q.isEmpty()) {
			int y = q.peek().y;
			int x = q.peek().x;
			int idx = q.peek().idx;
			int fuel = q.poll().fuel;

			// 가능한 승객을 찾았지만 다른 승객의 행, 열이 작은 경우
			if (client_find) {
				if(isVaild(y, x, fuel)){
					taxi = new Taxi(start[y][x], y, x, fuel);
				}
				continue;
			}

			if (start[y][x] >= 1) {
				taxi = new Taxi(start[y][x], y, x, fuel);
				client_find = true;
				continue;
			}

			if (client_find) continue;

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

				if (ny <= 0 || nx <= 0 || ny > N || nx > N) continue;
				if (visit[ny][nx] || start[ny][nx] == -1) continue;
				if (fuel < 1) continue;

				visit[ny][nx] = true;
				q.offer(new Taxi(idx, ny, nx, fuel - 1));
			}
		}

		if (!client_find) taxi = null;
		else start[taxi.y][taxi.x] = 0;
	}

	public static boolean isVaild(int y, int x, int f) {
		if (f > taxi.fuel && start[y][x] >= 1) {
			return true;
		} else if (f == taxi.fuel && start[y][x] >= 1) {
			if (y < taxi.y) {
				return true;
			} else if (y == taxi.y) {
				if (x < taxi.x) {
					return true;
				}
			}
		}
		return false;
	}

	public static void findToDestination() {
		Queue<Taxi> q = new LinkedList<>();
		boolean[][] visit = new boolean[N+1][N+1];

		visit[taxi.y][taxi.x] = true;
		q.offer(taxi);

		while (!q.isEmpty()) {
			int y = q.peek().y;
			int x = q.peek().x;
			int idx = q.peek().idx;
			int fuel = q.poll().fuel;

			if (goal[idx][y][x] == idx) {
				taxi = new Taxi(idx, y, x, fuel + (taxi.fuel - fuel) * 2);
				return;
			}

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

				if (ny <= 0 || nx <= 0 || ny > N || nx > N) continue;
				if (visit[ny][nx] || goal[idx][ny][nx] == -1) continue;
				if (fuel < 1) continue;

				visit[ny][nx] = true;
				q.offer(new Taxi(idx, ny, nx, fuel - 1));
			}
		}

		taxi = null;
	}
}