BOJ 19238 스타트 택시(JAVA) 🚕

구조화

행, 열

1. 거리가 가까운 고객 찾기
   • 고객이면 2, 3, 4... 도착지는 n-2번째 배열로 [0][1][2] 짝을 이루게 설정
2. 고객까지 가기
3. 이동 시엔 연료 - 도착 후 이동 경로만큼 연료 +
   • 도착 후는
     1. if(map[nx][ny]>1) → 고객을 만남
     2. 고객부터 목적지까지 bfs
     3. 목적지 도달하면 연료+이동 경로

소스 코드

import java.io.*;
import java.util.*;

public class Main {

	static int N, M, E, cuCnt, taCnt, max = Integer.MAX_VALUE; // N: 행, 열 M: 고객수 E: 연료량
	static int[][] map, distance;
	// static boolean[][] visited;
	static int startX, startY;
	static int cx, cy, tx, ty;
	static List<int[]> finish = new ArrayList<>();

	// 상하좌우
	// 작은 행 작은 열 우선
	static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		map = new int[N + 1][N + 1];
		distance = 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());
			}
		}

		st = new StringTokenizer(br.readLine());
		startX = Integer.parseInt(st.nextToken());
		startY = Integer.parseInt(st.nextToken());

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int fx = Integer.parseInt(st.nextToken());
			int fy = Integer.parseInt(st.nextToken());

			map[x][y] = i + 2;
			finish.add(new int[] { fx, fy });

			//System.out.println(map[x][y]);
			//System.out.println(finish.get(i)[0]+" "+finish.get(i)[1]);
		}
		// ---

		// 고객 수만큼
		while (M > 0) {
			// 실행할 때마다 초기화
			init();
			// 고객을 찾아요(택시->고객)
			customer();
			// 조건
			if (E <= cuCnt)
				break;
			// 실행문(연료소갈)
			E -= cuCnt;
			
			tx = finish.get(map[cx][cy] - 2)[0];
			ty = finish.get(map[cx][cy] - 2)[1];
			// 고객 만났으니깐 없애기
			map[cx][cy] = 0;
			// 택시옮기기

			//////////////////////////////////
			init();
			// 집에 데려다 주어요(고객->집)
			taxi();
			// 조건
			if (E < taCnt)
				break;
			// 실행문(연료충전)
			E += taCnt;
			// 고객 수 줄어듦(임무 완수)
			M--;
			// 택시옮기기
			startX = tx;
			startY = ty;
		}
		
		if(M > 0) E = -1;
		System.out.println(E);
		
	}

	public static void init() {
		cuCnt = taCnt = max;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				distance[i][j] = -1;
			}
		}
	}

	public static void customer() {

		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] { startX, startY });
		distance[startX][startY] = 0;

		// 고객이라면
		if (map[startX][startY] > 1) {
			cx = startX;
			cy = startY;
			cuCnt = distance[startX][startY];
		}

		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0];
			int y = cur[1];

			for (int w = 0; w < 4; w++) {
				int nx = x + way[w][0];
				int ny = y + way[w][1];

				// 경계 체크와 장애물 체크
				if (nx >= 0 && nx < N+1 && ny >= 0 && ny < N+1 && map[nx][ny] != 1 && distance[nx][ny] == -1) {

					distance[nx][ny] = distance[x][y] + 1;

					// 고객 만남
					if (map[nx][ny] > 1) {
						if (distance[nx][ny] == cuCnt) {
							if (nx == cx) {
								if (ny < cy) {
									cuCnt = distance[nx][ny];
									cx = nx;
									cy = ny;
								}
							} else if (nx < cx) {
								cuCnt = distance[nx][ny];
								cx = nx;
								cy = ny;
							}
						} else if (distance[nx][ny] < cuCnt) {
							cuCnt = distance[nx][ny];
							cx = nx;
							cy = ny;
						}
					}
					queue.add(new int[] { nx, ny });
				}

			}

		}
	}

	public static void taxi() {

		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] { cx, cy });
		distance[cx][cy] = 0;

		while (!queue.isEmpty()) {

			int[] cur = queue.poll();
			int x = cur[0];
			int y = cur[1];

			for (int w = 0; w < 4; w++) {
				int nx = x + way[w][0];
				int ny = y + way[w][1];

				// 경계 체크와 장애물 체크
				if (nx >= 0 && nx < N+1 && ny >= 0 && ny < N+1 && map[nx][ny] != 1 && distance[nx][ny] == -1) {
					distance[nx][ny] = distance[x][y]+1;
					
					// 목적지 도달
					if (nx == tx && ny == ty) {
						taCnt = distance[nx][ny];
					}
					queue.add(new int[] { nx, ny });
				}

			}
		}
	}
}