[BAEKJOON] 19238. 스타트 택시

 

문제링크

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

19238번: 스타트 택시

 

각 승객들의 모든 도착지와 출발지의 경로를 사전에 구해놓으면

시간초과로 절대 해결할 수 없는 문제이다.

 

그때그때 최선의 경우를 찾아서 그 경로로만 이동해야 한다.

 

package acmicpc.Gold4;

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

public class 스타트_택시 {

	static int n, m, k, map[][], ans, startR, startC;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static Person[] person;
	static class Person{
		int sr, sc, er, ec;

		public Person(int sr, int sc, int er, int ec) {
			super();
			this.sr = sr;
			this.sc = sc;
			this.er = er;
			this.ec = ec;
		}
		
	}
	static class Point implements Comparable<Point>{
		
		int r;
		int c;
		int cnt;
		int fuel;
		
		public Point(int r, int c, int cnt, int fuel) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.fuel = fuel;
		}

		@Override
		public int compareTo(Point o) {
			if(fuel < o.fuel) return 1;
			else if (fuel > o.fuel) return -1;
			else {
				if(r < o.r) return -1;
				else if (r > o.r) return 1;
				else {
					if(c < o.c ) return -1;
					else return 1;
				}
			}
		}
	}
	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());
		k = Integer.parseInt(st.nextToken());
		
		map = new int[n + 1][n + 1];
		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());
				if(map[i][j] > 0) {
					map[i][j] = 1000;
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		startR = Integer.parseInt(st.nextToken());
		startC = Integer.parseInt(st.nextToken());
		person = new Person[m + 1];
		
		for(int i = 1 ; i <= m ; i++) {
			st = new StringTokenizer(br.readLine());
			
			// 출발지
			int sr = Integer.parseInt(st.nextToken());
			int sc = Integer.parseInt(st.nextToken());
			
			map[sr][sc] = i;
		
			// 도착지
			int er = Integer.parseInt(st.nextToken());
			int ec = Integer.parseInt(st.nextToken());
			
			person[i] = new Person(sr,sc,er,ec);
			
		}

		for(int i = 0 ; i < m ; i++) {
			check(startR, startC);
			if(k == -1) break;
		}
		System.out.println(k);
		
	}
	
	public static void check(int r, int c) {
		
		PriorityQueue<Point> pq = new PriorityQueue<>();
		pq.add(new Point(r,c,0,k));
		boolean[][] visited = new boolean[n + 1][n + 1];
		visited[r][c] = true;
		int sr = 0;
		int sc = 0;
		int to = 0;
		
		while(!pq.isEmpty()) {
			
			Point q = pq.poll();

			if(q.fuel < 0) continue;
			
			if(map[q.r][q.c] > 0 && map[q.r][q.c] != 1000 ) {
				sr = q.r;
				sc = q.c;
				to = map[q.r][q.c];
				k = q.fuel;
				break;
			}
			
			for(int d = 0 ; d < 4 ; d++) {
				int nr = q.r + dr[d];
				int nc = q.c + dc[d];
				
				if(nr <= 0 || nc <= 0 || nr > n || nc > n) continue;
				if(visited[nr][nc] || map[nr][nc] == 1000) continue;
				
				visited[nr][nc] = true;
				pq.add(new Point(nr, nc, q.cnt + 1, q.fuel - 1));
				
			}
			
		}
		
		if(to == 0) {
			k = -1;
			return;
		} else {
			go(sr, sc, to);
		}
		
		
		
	}
	
	public static void go(int sr, int sc, int to) {
		
		map[sr][sc] = 0;
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(sr, sc, 0, k));
		boolean[][] visited = new boolean[n + 1][n + 1];
		visited[sr][sc] = true;
		boolean flag = false;
		
		while(!queue.isEmpty()) {
			
			Point q = queue.poll();

			if(q.fuel < 0) continue;
			
			if(q.r == person[to].er && q.c == person[to].ec) {
				flag = true;
				k = q.fuel + q.cnt * 2;
				map[sr][sc] = 0; 
				startR = q.r;
				startC = q.c;
				break;
			}
			
			for(int d = 0 ; d < 4 ; d++) {
				int nr = q.r + dr[d];
				int nc = q.c + dc[d];
				
				if(nr <= 0 || nc <= 0 || nr > n || nc > n) continue;
				if(visited[nr][nc] || map[nr][nc] == 1000) continue;
				
				visited[nr][nc] = true;
				queue.add(new Point(nr, nc, q.cnt + 1, q.fuel - 1));
				
			}
			
		}
		
		if(!flag) {
			k = -1;
			return;
		}
	}
	
}