[백준 / JAVA] 19238. 스타트 택시 (G2)

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

 

어렵지 않고 풀이도 바로 보이는 문제이다. 아마 승객 탑승 지점과 도착 지점을 저장하는 방식 정도만 사람마다 다를 것 같다.

나는 탑승 지점 지도를 따로 만들었는데, 2차원 맵에 인덱스를 저장하고 싶을 때 문제에 벽 같은 조건이 들어가 있어 곤란하다면 맵을 분리하면 편하다.(어차피 벽이 쓰이는 곳은 bfs에서 뿐임)

도착 지점은 리스트로 저장했는데, 도착 지점은 중복될 수 있다는 점이 이 문제의 유일한 함정 같았다. 이걸 고려 안 해서 틀리는 경우가 있을진 모르겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		fuel = Integer.parseInt(st.nextToken());
		map = new int[N][N]; // 벽 위치 저장
		startMap = new int[N][N]; // 탑승 위치 저장
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		taxiPoint = new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
		for (int i = 1; i < M + 1; i++) {
			st = new StringTokenizer(br.readLine());
			startMap[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = i;
			destList.add(new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1));
		}
		for (int i = 0; i < M; i++) {
			if (!bfs2(bfs1())) {
				System.out.println(-1);
				return;
			}
		}
		System.out.println(fuel);
	}

	static int N, M, fuel, map[][], startMap[][], dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
	static ArrayList<Point> destList = new ArrayList<>(); // 목적지가 다르다는 보장이 없어서 리스트에 저장
	static Point taxiPoint;

	static boolean bfs2(Point startPoint) { // 출발점과 도착점 거리 측정
		if (startPoint == null)
			return false;
		Point destPoint = destList.get(startMap[startPoint.row][startPoint.col] - 1);
		Deque<Point> q = new LinkedList<>();
		boolean visited[][] = new boolean[N][N];
		int dist = 0; // 거리
		q.add(startPoint);
		visited[startPoint.row][startPoint.col] = true;
		while (!q.isEmpty()) {
			int size = q.size();
			if (++dist > fuel)
				return false;
			for (int i = 0; i < size; i++) {
				Point cur = q.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur.row + dr[d];
					int nc = cur.col + dc[d];
					if (nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc] || map[nr][nc] == 1) // 벽 체크
						continue;
					if (nr == destPoint.row && nc == destPoint.col) {
						startMap[startPoint.row][startPoint.col] = 0;
						taxiPoint = destPoint;
						fuel += dist;
						return true;
					}
					q.add(new Point(nr, nc));
					visited[nr][nc] = true;
				}
			}
		}
		return false;
	}

	static Point bfs1() { // 택시 시작점에서 가장 가까운 포인트 찾기
		if (startMap[taxiPoint.row][taxiPoint.col] > 0) // 택시 출발점 = 탑승위치
			return taxiPoint;
		Point startPoint = null;
		Deque<Point> q = new LinkedList<>();
		boolean visited[][] = new boolean[N][N];
		int dist = 0; // 거리
		q.add(taxiPoint);
		visited[taxiPoint.row][taxiPoint.col] = true;
		while (!q.isEmpty()) {
			int size = q.size();
			if (++dist > fuel)
				return null;
			for (int i = 0; i < size; i++) {
				Point cur = q.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur.row + dr[d];
					int nc = cur.col + dc[d];
					if (nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc] || map[nr][nc] == 1) // 벽 체크
						continue;
					if (startMap[nr][nc] > 0) {
						if (startPoint == null)
							startPoint = new Point(nr, nc);
						else if (startPoint.row > nr) {
							startPoint = new Point(nr, nc);
						} else if (startPoint.row == nr)
							if (startPoint.col > nc)
								startPoint = new Point(nr, nc);
					}
					q.add(new Point(nr, nc));
					visited[nr][nc] = true;
				}
			}
			if (startPoint != null) {
				fuel -= dist;
				return startPoint;
			}
		}
		return startPoint; // null
	}

	static class Point {
		int row, col;

		public Point(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
	}
}