[Java] BOJ 19238번 스타트 택시

[Java] BOJ 19238번 스타트 택시

풀이

문제에서 주어진 조건대로 처리하여 해결했습니다.

자세한 내용은 코드의 주석을 참고해주세요.

코드

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 { // 택시를 이동할 때 사용할 클래스 public static class Taxi { int y, x, fuel; public Taxi(int y, int x, int fuel) { this.y = y; this.x = x; this.fuel = fuel; } } // 손님의 위치정보와 현재 택시의 연료를 저장하는 클래스 public static class Info implements Comparable { int st_y, st_x, en_y, en_x, curFeul; public Info(int st_y, int st_x, int en_y, int en_x, int curFeul) { this.st_y = st_y; this.st_x = st_x; this.en_y = en_y; this.en_x = en_x; this.curFeul = curFeul; } @Override public int compareTo(Info o) { int diff = Integer.compare(this.st_y, o.st_y); return (diff == 0) ? Integer.compare(this.st_x, o.st_x) : diff; } } public static int N, M, initFuel, answer; // 손님의 위치정보는 여러개 이므로 배열을 사용하여 저장 public static Info[] infos; // 문제에서 주어진 우선순위에 맞는 손님을 태우기 위해 사용 public static PriorityQueue pq; // 택시가 이동 시 방문한 위치에는 다시 방문하지 않도록 하기 위한 배열 public static boolean[][] visited; // 맵의 정보를 저장 public static int[][] map; 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()); initFuel = Integer.parseInt(st.nextToken()); map = new int[N][N]; 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(), " "); int taxi_y = Integer.parseInt(st.nextToken()) - 1; int taxi_x = Integer.parseInt(st.nextToken()) - 1; infos = new Info[M]; for (int i = 0; i < M; ++i) { st = new StringTokenizer(br.readLine(), " "); int st_y = Integer.parseInt(st.nextToken()) - 1; int st_x = Integer.parseInt(st.nextToken()) - 1; int en_y = Integer.parseInt(st.nextToken()) - 1; int en_x = Integer.parseInt(st.nextToken()) - 1; // 고유한 손님의 번호를 알기위해 map에서 쓰이지않는 2이상의 수를 만들기위해 // +2를 해주어 맵에 표시 map[st_y][st_x] = i + 2; infos[i] = new Info(st_y, st_x, en_y, en_x, -1); } // 택시에 태운 손님의 수를 카운트 int cnt = 0; // 현재 택시의 연료를 저장 int curFuel = initFuel; for (int i = 0; i < M; ++i) { pq = new PriorityQueue<>(); // 현재 태울 수 있는 손님을 전부 구한다. findCustomer(taxi_y, taxi_x, curFuel); // 만약 우선순위큐가 비어있다면 이는 태울 손님이 없거나 연료가 다 떨어졌다는 의미이므로 if (pq.isEmpty()) { // 정지 break; } Info info = pq.poll(); // 우선순위에 맞게 뽑힌 손님을 태우고 목적지까지 전진하고 남은 연료를 반환받는다 curFuel = go(info); // 남은 연료가 0보다 작다면 더이상 운행이 불가하므로 정지 if (curFuel <= 0) { break; } // 택시가 목적지에 도착했으므로 택시 위치 갱신 taxi_y = info.en_y; taxi_x = info.en_x; // 손님 수 카운트 cnt++; } if (cnt < M) { // 만약 M명의 손님을 전부 태우지 못했다면 System.out.println(-1); } else { // M명의 손님을 전부 태웠다면 System.out.println(curFuel); } } public static int[] dy = {-1, 1, 0, 0}; public static int[] dx = {0, 0, -1, 1}; public static void findCustomer(int y, int x, int curFuel) { // 연료가 가장 많이 남는 위치의 손님을 찾기위해 변수를 사용 int maxFuel = 0; visited = new boolean[N][N]; Queue q = new LinkedList<>(); q.offer(new Taxi(y, x, curFuel)); while (!q.isEmpty()) { Taxi taxi = q.poll(); // 만약 연료가 0보다 작다면 이동이 불가능 하므로 // 멈춘다. if (taxi.fuel < 0) { return; } // 손님의 위치이고 현재 남은 연료가 이전에 저장한 남은 연료보다 더 많이 남거나 같다면 if (map[taxi.y][taxi.x] > 1 && maxFuel <= taxi.fuel) { // 배열에서 손님 정보를 빼오기위해 +2를 한 숫자에서 -2를 한다. int customer = map[taxi.y][taxi.x] - 2; // 남은 연료를 기록 infos[customer].curFeul = taxi.fuel; // 문제에서 주어진 우선순위대로 뽑기위해 우선순위큐에 삽입 pq.offer(new Info(infos[customer].st_y, infos[customer].st_x, infos[customer].en_y, infos[customer].en_x, taxi.fuel)); // 남은 연료를 갱신 maxFuel = taxi.fuel; continue; } for (int i = 0; i < 4; ++i) { int ny = taxi.y + dy[i]; int nx = taxi.x + dx[i]; if (ny < 0 || nx < 0 || ny >= N || nx >= N) { continue; } if (!visited[ny][nx] && map[ny][nx] != 1) { q.offer(new Taxi(ny, nx, taxi.fuel - 1)); visited[ny][nx] = true; } } } } public static int go(Info info) { // 남은 연료를 반환하기 위함 int fuel = -1; // 현재 손님을 태웠으므로 0으로 변경 map[info.st_y][info.st_x] = 0; visited = new boolean[N][N]; Queue q = new LinkedList<>(); q.offer(new Taxi(info.st_y, info.st_x, info.curFeul)); visited[info.st_y][info.st_x] = true; while (!q.isEmpty()) { Taxi taxi = q.poll(); // 만약 연료가 0보다 더 작다면 // 더이상 이동할 수 없으므로 정지 if (taxi.fuel < 0) { break; } // 목적지에 도착했다면 if (taxi.y == info.en_y && taxi.x == info.en_x) { // 문제의 조건에 맞게 연료를 갱신 fuel = taxi.fuel + (info.curFeul - taxi.fuel) * 2; break; } for (int i = 0; i < 4; ++i) { int ny = taxi.y + dy[i]; int nx = taxi.x + dx[i]; if (ny < 0 || nx < 0 || ny >= N || nx >= N) { continue; } if (!visited[ny][nx] && map[ny][nx] != 1) { q.offer(new Taxi(ny, nx, taxi.fuel - 1)); visited[ny][nx] = true; } } } return fuel; } }

from http://comgong-man.tistory.com/239 by ccl(A) rewrite - 2021-09-17 12:01:37