[백준] 19238 스타트택시[JAVA]

문제링크: www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제를 보자마자 이전에 풀었던 삼성 유형 중 아기상어 문제가 떠올랐다. 

일부 조건만 제외하면 똑같이 풀면 된다.

현재 위치에서, 가진 연료로 가장 가까운 손님(여럿 있다면 위쪽일수록, 왼쪽일수록)을 태울 수 있으면 태우고 이동한다.

 

이동하면 손님을 목적지로 이동한 걸의 2배만큼 연료가 충전되며, 이 과정을 모든 손님을 목적지까지 이동할 수 있으면 남은 연료를, 없으면 -1을 출력하는 문제다.

//9시27분 시작
import java.io.*;
import java.util.*;
public class Main {
	
	public static class Node implements Comparable<Node>{
		int y;
		int x;
		public Node(){}
		public Node(int a,int b){
			y = a;
			x= b;
		}
		@Override
		public int compareTo(Node o) {
			if(this.y > o.y){
				return 1;
			}else if(y==o.y){
				if(this.x > o.x){
					return 1;
				}else{
					return -1;
				}
			}
			return -1;
		}
	}
	public static boolean endCustomer[] ;
	public static int [][]dir = {{-1,0},{0,1},{1,0},{0,-1}};
	public static int N,M,F;
	public static int [][]board;
	public static int taxiY,taxiX;
	public static int [] dest; //i번째 손님의 목적지까지의 거리
	public static int endCustomerCnt; 
	public static int custNum,neededFuel;
	public static int ans;
	public static Node destination[];
	public static boolean isBoundry(int y,int x){
		if(y <=0 || x<=0 || y>N || x >N ) return false;
		return true;
	}
	
	public static int calcDist(int sy,int sx, int dy,int dx){
		boolean visited[][] = new boolean[N+1][N+1];
		visited[sy][sx] = true;
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(sy,sx));
		int ret = 0;
		while(!q.isEmpty()){
			int q_size = q.size();
			for(int i=0;i<q_size;i++){
				Node cur = q.poll();
				if(cur.y == dy && cur.x == dx){
					return ret;
				}
				for(int j=0;j<4;j++){
					int ny = cur.y + dir[j][0];
					int nx = cur.x + dir[j][1];
					if(!isBoundry(ny,nx) || visited[ny][nx] || board[ny][nx] == -1)continue;
					visited[ny][nx] = true;
					q.offer(new Node(ny,nx));
				}
			}
			ret++;
		}
		return -1;
	}
	
	public static void pick(){
		
		boolean visited[][] = new boolean[N+1][N+1];
		visited[taxiY][taxiX] = true;
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(taxiY,taxiX));
		custNum = -1; neededFuel = 0;
		ArrayList<Node> candi = new ArrayList<Node>();
		while(!q.isEmpty()){
			int q_size = q.size();
			for(int i=0;i<q_size;i++){
				Node cur = q.poll();
				if(board[cur.y][cur.x] != -1 && board[cur.y][cur.x] != 0){
					if(!endCustomer[board[cur.y][cur.x]])
						candi.add(cur);
				}
				for(int j=0;j<4;j++){
					int ny = cur.y + dir[j][0];
					int nx = cur.x + dir[j][1];
					if(!isBoundry(ny,nx) || visited[ny][nx] || board[ny][nx]==-1)continue;
					visited[ny][nx] = true;
					q.offer(new Node(ny,nx));
				}
			}
			if(candi.size()>0){
				Collections.sort(candi);
				custNum = board[candi.get(0).y][candi.get(0).x];
				neededFuel += dest[custNum];
				taxiY = destination[custNum].y;
				taxiX = destination[custNum].x;
				return;
			}
			neededFuel++;
		}
	}
	
	public static void simul(){
		//현재 택시 위치에서 태울 손님을 정하고 거리를 구함.
		pick();
		//1.남은 손님이 존재하는데 손님을 태울 수 없으면 실패
		//2.손님을 태우고 목적지 까지 갈 수 없으면 실패
		if(custNum==-1 || neededFuel > F){
			ans = -1;
			return;
		}
		//정해진 손님을 목적지까지 바래다주고 연료 갱신
		F = F - neededFuel + dest[custNum]*2;
		//아직 태울 손님이 남았으면 시뮬 반복, 아니면 F 출력 => 끝
		endCustomerCnt++;
		endCustomer[custNum] = true;
		if(endCustomerCnt != M){
			simul();
		}else{
			ans = F;
		}
	}
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		F = Integer.parseInt(st.nextToken());
		board = new int[N+1][N+1];
		dest = new int[M+1];
		endCustomer = new boolean[M+1];
		destination = new Node[M+1];
		for(int i=1;i<=M;i++){
			destination[i] = new Node();
		}
		for(int i=1;i<=N;i++){
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++){
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j] == 1){
					board[i][j] = -1;
				}
			}
		}
		int idx=  1;
		st = new StringTokenizer(br.readLine());
		taxiY = Integer.parseInt(st.nextToken());
		taxiX = Integer.parseInt(st.nextToken());
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine());
			int startY = Integer.parseInt(st.nextToken());
			int startX = Integer.parseInt(st.nextToken());
			int destY = Integer.parseInt(st.nextToken());
			int destX = Integer.parseInt(st.nextToken());
			destination[idx].y = destY;
			destination[idx].x = destX;
			board[startY][startX] = idx;
			dest[idx++] = calcDist(startY,startX,destY,destX);
			if(dest[idx-1]==-1){
				System.out.println(-1);
				System.exit(0);
			}
		}
		
		simul();
		System.out.println(ans);
	}

}