[백준] 19238 스타트 택시

문제

---

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

19238번: 스타트 택시

 

 

문제에 설명이 길어서 들어가서 확인 해보는 것이 좋을 거 같다.

 

풀이

---

2가지 경우로 나눠서 풀었다. 2가지 경우 모두 BFS를 사용하였다.

1. 승객을 찾아서 태우는 경우

2. 승객을 목적지로 데려다 주는경우

 

이 두가지 경우에는 종료 조건이 다르다.

1번의 경우에는 손님을 태웠을 때 연료가 0 이 되면 실패다.

2번의 경우에는 손님을 목적지에 데려다주고 연료가 0이 되면 실패가 아니다.

 

따라서 두가지 경우로 나눠서 함수를 작성하여 풀었다.

 

1번의 경우에는 같은 거리에 있는 승객이 많은 경우 행이 작은것 부터 그래도 많다면 열이 작은 순으로 태운다. ( 우선순위 큐를 활용하여 정렬하면서 풀었다.)

 

<1번 경우 코드>

public static int findPassenger(taxi t) {
	
	int x = t.x;
	int y = t.y;
	
	boolean[][] visited = new boolean[N][N];
	visited[x][y] = true;
	
	PriorityQueue<point> pq = new PriorityQueue<>();
	pq.add(new point(x, y, 0));
	while(!pq.isEmpty()){
		
		point top = pq.poll();
		
		if(passengerMap[top.x][top.y] != null) {
			t.passenger = passengerMap[top.x][top.y];
			passengerMap[top.x][top.y] = null; 
			
			t.x = top.x;
			t.y = top.y;				
			return top.times;
		}
		
		if(top.times >= t.fuel) {
			return -1;
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			
			int nx = top.x + move[i][0];
			int ny = top.y + move[i][1];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] || map[nx][ny] == 1) { continue;}
			
			visited[nx][ny] = true;
			pq.add(new point(nx, ny, top.times + 1));
		}			
	}
	
	return -1;
}

이 경우는 횟수가 작은 것으로 정렬이 돼있기 때문에 현재의 point 가 연료양을 넘으면 그 뒤는 보지 않아도 된다.

 

이때 passenger 은 미리 목적지 위치를 저장하여 passengerMap으로 구성하여 해당 위치에 승객이 있는 지 쉽게 찾게하였다.

 

2번의 경우는 더욱 간단하다. 해당 승객의 목적지까지 갈수있는 최단거리를 BFS 를 통해 찾으면 된다.

 

<2번경우>

public static int goPassenger(taxi t) {
	
	passenger now = t.passenger;
	
	int x = t.x;
	int y = t.y;
	
	boolean[][] visited = new boolean[N][N];
	visited[x][y] = true;
	Queue<point> queue = new LinkedList<>();
	
	queue.add(new point(x, y, 0));
	while(!queue.isEmpty()) {
		
		point top = queue.poll();
		
		if(top.x == now.endX && top.y == now.endY) {
			t.passenger = null;
			t.x = top.x;
			t.y = top.y;
			return top.times;
		}
		
		if(top.times >= t.fuel) {
			continue;
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			int nx = top.x + move[i][0];
			int ny = top.y + move[i][1];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] || map[nx][ny] == 1) {continue;}
			
			visited[nx][ny] = true;
			queue.add(new point(nx, ny, top.times + 1));
		}
	}		
	return -1;
}

 

이렇게 결과 값을 받았을 때 -1 이면 모두 데려다 줄 수 없다는 것이므로 -1을 출력하게 하였다.

M 명을 모두 데려다 줄 수 있는 경우 그 때의 값을 출력하게 하였다.

 

<전체코드>

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

public class Main {
	
	
	static int N, M, fuel;
	static int[][] map;
	static passenger[][] passengerMap;
	static int[][] move = { {-1,0}, {1,0}, {0,-1}, {0,1}};
	static int answer = -1;
	
	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		N = parseInt(st.nextToken());
		M = parseInt(st.nextToken());
		fuel = parseInt(st.nextToken());
		
		map = new int[N][N];
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			for(int j = 0 ; j < N ; j++) {
				map[i][j] = parseInt(st.nextToken());
			}
		}
	
		st = new StringTokenizer(bufferedReader.readLine());
		taxi t = new taxi(parseInt(st.nextToken()) - 1, parseInt(st.nextToken()) - 1, fuel, null);
		
		passengerMap = new passenger[N][N];
		for(int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			int sX = parseInt(st.nextToken()) - 1;
			int sY = parseInt(st.nextToken()) - 1;
			int eX = parseInt(st.nextToken()) - 1;
			int eY = parseInt(st.nextToken()) - 1;
			
			passengerMap[sX][sY] = new passenger(eX, eY);
		}
		
		start(t);
		System.out.println(answer);
	}
	
	public static int findPassenger(taxi t) {
		
		int x = t.x;
		int y = t.y;
		
		boolean[][] visited = new boolean[N][N];
		visited[x][y] = true;
		
		PriorityQueue<point> pq = new PriorityQueue<>();
		pq.add(new point(x, y, 0));
		while(!pq.isEmpty()){
			
			point top = pq.poll();
			
			if(passengerMap[top.x][top.y] != null) {
				t.passenger = passengerMap[top.x][top.y];
				passengerMap[top.x][top.y] = null; 
				
				t.x = top.x;
				t.y = top.y;				
				return top.times;
			}
			
			if(top.times >= t.fuel) {
				return -1;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				
				int nx = top.x + move[i][0];
				int ny = top.y + move[i][1];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] || map[nx][ny] == 1) { continue;}
				
				visited[nx][ny] = true;
				pq.add(new point(nx, ny, top.times + 1));
			}			
		}
		
		return -1;
	}
	
	public static int goPassenger(taxi t) {
		
		passenger now = t.passenger;
		
		int x = t.x;
		int y = t.y;
		
		boolean[][] visited = new boolean[N][N];
		visited[x][y] = true;
		Queue<point> queue = new LinkedList<>();
		
		queue.add(new point(x, y, 0));
		while(!queue.isEmpty()) {
			
			point top = queue.poll();
			
			if(top.x == now.endX && top.y == now.endY) {
				t.passenger = null;
				t.x = top.x;
				t.y = top.y;
				return top.times;
			}
			
			if(top.times >= t.fuel) {
				continue;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				int nx = top.x + move[i][0];
				int ny = top.y + move[i][1];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] || map[nx][ny] == 1) {continue;}
				
				visited[nx][ny] = true;
				queue.add(new point(nx, ny, top.times + 1));
			}
		}		
		return -1;
	}
	
	public static void start(taxi t) {
		
		for(int i = 0 ; i < M ; i++) {
			int useFuel = findPassenger(t);
			if(useFuel == -1) {
				return;
			}
			
			t.fuel -= useFuel;
			
			useFuel = goPassenger(t);
			
			if(useFuel == -1) {
				return;
			}
			
			t.fuel += useFuel;
		}
		
		answer = t.fuel;
		return;
	}
	
	static class point implements Comparable<point>{
		int x, y;
		int times;
		
		point(int x, int y, int times){
			this.x = x;
			this.y = y;
			this.times = times;
		}
		
		@Override
		public int compareTo(point o) {
			if(this.times == o.times) {
				if(this.x == o.x) {
					return this.y - o.y;
				}
				
				return this.x - o.x;
			}
			
			return this.times - o.times;
		}
	}
	
	static class passenger{
		int endX, endY;
		
		passenger(int eX, int eY){
			this.endX = eX;
			this.endY = eY;
		}
	}
	
	static class taxi{
		int x, y, fuel;
		passenger passenger;
			
		taxi(int x, int y, int fuel, passenger p){
			this.x = x;
			this.y = y;
			this.fuel = fuel;
			this.passenger = p;
		}
	}
}