[BOJ 19238] 스타트택시

문제

• BOJ 19238
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

BFS+시뮬레이션 문제이다.
아직 풀지 못한 아기상어 보다는 어떻게 구현해야 할지 답이 왔다. 그러나 생각해야할 조건들이 있어서 함정에 빠지기 쉽다. 내가 생각한 구현 방식은 다음과 같다.

1. 현재 택시좌표를 기준으로 상,하,좌,우를 탐색해서 손님좌표가 있는지 확인 후 없으면 큐에 넣는다.
   만약 손님좌표를 만나면 현재 큐에 있는 모든 손님좌표를 찾으면서 행과 열을 비교한 후 최종 손님좌표를 정하고 현재 연료에서 이동거리만큼 빼준다. 그리고 택시좌표를 손님좌표로 이동시킨다.
2. 해당 손님 좌표에 저장된 손님번호로 ends[]배열에 접근해 목적지를 알아낸다. 그리고 다시 현재 택시좌표를 기준으로 현재 좌표,상,하,좌,우를 탐색해서 목적지좌표가 있는지 확인 후 없으면 큐에 넣는다.
   만약 목적지좌표를 만나면 현재 연료에서 이동한 거리만큼 빼주고, 다시 이동한 거리의 2배를 더한다.
   
   이때, 주의할 점은 출발지와 목적지가 같은 경우와 택시와 손님좌표가 같은 경우이다.
   처음에 이 조건을 고려해주지 않아서 틀렸었다.
   이를 모두 고려해주기 위해 큐에 탐색 전 if문으로 조건을 걸어서 맞다면 각각의 boolean형 변수를 true로 바꾼후 함수를 빠져나오도록 해주었다.
   boolean형 변수는 손님좌표를 찾은 경우, 목적지좌표를 찾은 경우에 대한 결과로 다음 단계를 가기전 조건으로 사용해 시간을 단축시키도록 하였다.

코드

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 Boj19238 {

	static int[][] map; //맵
	static int N; //크기
	static int M; //승객 수
	static int fuel; //연료의 양
	static int taxiX, taxiY; //택시 좌표
	static int userX, userY; //현재 선택된 승객 좌표
	static boolean isGo; //택시가 연료안에 갈 수 있는지
	static boolean isEnd; //택시가 연료 안에 목적지에 갈 수 있는지
	static Point[] ends; //각 승객의 목적지 저장
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	static boolean[][] visited;
	static boolean success = false; //모든 승객을 성공적으로 데려다줬다면

	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];
		ends = new Point[M+1];

		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				int input = Integer.parseInt(st.nextToken());
				if(input == 1) map[i][j] = -1; ///벽이면 -1로 표시
			}
		}

		st = new StringTokenizer(br.readLine());
		taxiX = Integer.parseInt(st.nextToken());
		taxiY = Integer.parseInt(st.nextToken());

		for(int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()); //승객 출발 x
			int y = Integer.parseInt(st.nextToken()); //승객 출발 y
			map[x][y] = i; //승객번호 표시
			ends[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		for(int m=0; m<M; m++) { //M번 진행
			getUser(); //승객 찾기
			if(isGo) { //승객에게 갈수 있다면
				go();
				if(isEnd) success = true; //목적지로 갈수있다면
				else{
					success = false;
					break;
				}
			}
			else{
				success = false;
				break;
			}
		}

		if(success) System.out.println(fuel);
		else System.out.println(-1);
	}

	//목적지로 이동
	private static void go() {
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(taxiX, taxiY)); //현재 출발좌표(택시 좌표)를 넣고
		int size = 0; //현재 큐의 사이즈
		int dist = 0; //현재까지 지나온 거리
		int num = map[userX][userY]; //승객번호
		int endX = ends[num].x; //목적지
		int endY = ends[num].y;
		isEnd = false;
		visited = new boolean[N+1][N+1];

		//출발지와 목적지가 같은 경우
		if(taxiX == endX && taxiY == endY) {
			isEnd = true;
			return;
		}

		while(!queue.isEmpty()) {
			++dist;
			size = queue.size();
			for(int s=0; s<size; s++) {

				Point now = queue.poll();
				for(int d=0; d<4; d++) {
					int ni = now.x + di[d];
					int nj = now.y + dj[d];

					if(ni>=1 && ni<=N && nj>=1 && nj<=N && map[ni][nj] != -1 && !visited[ni][nj]) { //범위안에 들고 벽이 아니면
						if(ni==endX && nj==endY) { //목적지에 도달했다면
							if(fuel - dist >= 0) {
								fuel = (fuel-dist) + (dist*2);
								isEnd = true;
								map[userX][userY] = 0;
								taxiX = ni;
								taxiY = nj;
							}
							return;
						}else{
							visited[ni][nj] = true;
							queue.add(new Point(ni, nj));
						}
					}
				}//상하좌우 탐색 완료
			}//같은 거리에 있는 좌표탐색 완료
		}//탐색 모두 완료
	}

	//최단거리에 있는 승객 좌표 가져오기
	private static void getUser() {
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(taxiX, taxiY)); //현재 출발좌표(택시 좌표)를 넣고
		int size = 0; //현재 큐의 사이즈
		int dist = 0; //현재까지 지나온 거리
		userX = Integer.MAX_VALUE;
		userY = Integer.MAX_VALUE;
		boolean isFind = false; //태울 수 있는 승객을 찾았다면
		isGo = false; //택시가 연료안에 갈수있는지
		visited = new boolean[N+1][N+1];

		//택시와 출발지가 동일한 경우
		if(map[taxiX][taxiY]>0) {
			userX = taxiX;
			userY = taxiY;
			isGo = true;
			return;
		}

		while(!queue.isEmpty()) {
			++dist;
			size = queue.size();
			for(int s=0; s<size; s++) {
				Point now = queue.poll();
				for(int d=0; d<4; d++) {
					int ni = now.x + di[d];
					int nj = now.y + dj[d];

					if(ni>=1 && ni<=N && nj>=1 && nj<=N && map[ni][nj] != -1 && !visited[ni][nj]) { //범위안에 들고 벽이 아니면
						if(map[ni][nj] != 0 && ni < userX) { //승객이고 행번호가 더 작다면
							userX = ni;
							userY = nj; //얘를 승객으로 선택
							isFind = true;
						}if(map[ni][nj] != 0 && ni==userX && nj < userY) { //승객이고 행도 같은데 열번호가 더 작다면
							userX = ni;
							userY = nj; //얘를 승객으로 선택
							isFind = true;
						}else{
							visited[ni][nj] = true; //방문표시
							queue.add(new Point(ni, nj)); //큐에 넣기
						}
					}
				}//상하좌우 탐색 완료
			}//같은 거리에 있는 좌표탐색 완료
			if(isFind) { //승객을 찾았다면
				//현재 연료로 갈수 있는지 계산
				if(fuel-dist > 0) {
					isGo = true;
					taxiX = userX; //여기로 택시 이동
					taxiY = userY;
					fuel -= dist;
				}
				else{
					isGo = false;
				}
				return; //함수 종료
			}
		}//탐색 모두 완료
	}

	static class Point{
		int x;
		int y;

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