BOJ - 스타트택시 19238번 (JAVA)

❓ 문제 - 백준 스타트택시 19238번 - JAVA 풀이법

 

출처 

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

19238번: 스타트 택시

 

 

 

📝 문제해결법

1. 이 문제는 BFS+구현으로 풀었다.

• 2차원배열 map으로 활동할 영역에 대한 정보를 관리한다.
• cus_map으로 손님의 출발지의 위치를 저장하고, cus로 손님의 출발지 x, y 도착치 x,y를 저장해서 관리한다.
• 택시는 모든 손님을 다 태울 때나 운행이 종료될까지 운행 되는데 bfs1()함수를 통해 현재 택시의 위치에서 손님들까지의 거리를 계산하고 거리의 최소, 거리가 같으면 행의 최소, 행이 같으면 열의 최소의 조건으로 정렬한다. 따라서 정렬 조건에 맞춰 태울 손님을 한 명 고른다. 여기서 주의할 점은 남은 손님들 중에 벽 때문에 갈 수 없는 손님이 있으면 운행을 강제 종료한다.
• 정렬 조건에 맞춰 태울 손님을 한 명 고르고 해당 손님의 목적지까지의 최단거리를 bfs2()를 통해 구한다. 이때도 손님의 도착지가 갈 수 없는 곳이라면 -1을 출력하고 운행을 종료한다. 
• 손님의 출발지로 갈 수 있고, 해당 출발지에서 목적지까지 갈 수 있으면 두 거리의 합을 현재 남은 오일이랑 비교해서 남은 오일양으로 갈 수 없다면 운행을 종료한다. 

 

 

💻 소스코드

// BOJ - 스타트 택시(19238번)
// BFS

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

public class Main_19238 {
	public static int n, m, oil, people;
	public static int[][] map;
	public static int[][] cus_map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static boolean[] check;
	public static int t_x, t_y;
	public static class Node implements Comparable<Node>{
		int x;
		int y;
		int dis;
		public Node(int x, int y, int dis) {
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
		@Override
		public int compareTo(Node o) {
			if(this.dis == o.dis) {
				if(this.x == o.x) {
					return this.y - o.y;
				} 
				return this.x - o.x;
			}
			return this.dis - o.dis;
		}
	}
	public static int[][] cus;

	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());
		oil = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		cus = new int[m+1][4];
		cus_map = new int[n][n];
		check = new boolean[m+1];
		
		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(), " ");
		t_x = Integer.parseInt(st.nextToken())-1;
		t_y = Integer.parseInt(st.nextToken())-1;
		
		for(int i=1;i<=m;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<4;j++) {
				int num = Integer.parseInt(st.nextToken())-1;
				cus[i][j] = num;
			}
			cus_map[cus[i][0]][cus[i][1]] = i;
		}
		
		people = m;
		boolean end = false;
		while (true) {
			if(people == 0) {
				break;
			}
			
			// 손님 고르기
			Node node = bfs1();
			if(node == null) {
				end = true;
				break;
			}
			int cus_num = cus_map[node.x][node.y];
			// 손님 데려다 주기
			
			int cal1 = node.dis;
			int cal2 = bfs2(node.x, node.y, cus[cus_num][2], cus[cus_num][3]);
	
			
			if(oil < cal1+cal2 || cal2 == -1) {
				end = true;
				break;
			}
			
			oil -= (cal1+cal2);
			oil += (cal2 * 2);
			check[cus_num] = true;
			cus_map[node.x][node.y] = 0;
			t_x = cus[cus_num][2];
			t_y = cus[cus_num][3];
			people--;
				
		}
		if(end) System.out.println(-1);
		else System.out.println(oil);
	}
	
	public static Node bfs1() {
		boolean[][] visited = new boolean[n][n];
		Queue<Node> q = new LinkedList<>();
		PriorityQueue<Node> pq = new PriorityQueue<>();
		visited[t_x][t_y] = true;
		q.offer(new Node(t_x, t_y, 0));
		while(!q.isEmpty()) {
			Node node = q.poll();
			if(cus_map[node.x][node.y] >= 1 && !check[cus_map[node.x][node.y]]) {
				pq.add(new Node(node.x, node.y, node.dis));
			}
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny] && map[nx][ny] != 1) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, node.dis+1));
					}
				}
			}
		}
		if(pq.isEmpty()) return null;
		return pq.poll();
		
	}
	
	public static int bfs2(int s_x, int s_y, int e_x, int e_y) {
		boolean[][] visited = new boolean[n][n];
		Queue<Node> q = new LinkedList<>();

		visited[s_x][s_y] = true;
		q.offer(new Node(s_x, s_y, 0));
		int dis = -1;
		while(!q.isEmpty()) {
			Node node = q.poll();
			if(node.x == e_x && node.y == e_y) {
				return node.dis;
			}
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny] && map[nx][ny] != 1) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, node.dis+1));
					}
				}
			}
		}
		return dis;
	}

}