[java] 백준(BOJ) - 스타트택시

문제

백준-스타트택시
모든 승객을 출발지부터 목적지까지 데려다 준 후 남은 연료를 출력하는 문제.

각 승객은 출발지와 목적지가 있다
현재 택시 위치에서 가장 가까운 승객의 위치까지 이동한다(연료 소모)
승객의 목적지까지 이동한다(연료소모)
목적지에 승객을 성공적으로 이동시키면, 이동하는데 소모한 연료의 2배를 얻는다
모든 승객을 목적지에 데려다주지 못한 경우, 실패한다.
중간의 이동과정에서 연료가 부족한 경우, 실패한다.

풀이

ㅎㅎ엄청 많이 시도해서 푼 문제..
시간초과, 틀렸습니다를 반복하다가 찾은 포인트를 중점으로 풀이를 적어보려한다.

1. 어떤 승객을 태울 지 선택할 때

A승객과 B승객까지의 거리가 같다면 행 번호가 작은 승객을 우선으로한다.
행 번호가 같다면, 열 번호가 작은 승객을 우선으로 한다.
예) (2,3) 승객과 (4,5) 승객까지의 거리가 같다면 (2,3) 예) (1,3) 승객과 (1,5) 승객까지의 거리가 같다면 (1,3) 문제를 제대로 안읽어서 생긴 실수 ㅠㅠ

• 4방향을 체크할때 주의
  x = {-1,0,1,0}, y={0,-1,0,1} 이런식으로 배열의 값을 이용해 어느 방향을 우선으로 봐야할지 조절하면 ❌
  위의 x,y로 보면 상, 좌, 하, 우 순으로 우선순위를 가지고 있다
  

이 경우에 택시의 위치에서 우선순위대로 아래쪽의 승객을 먼저 태우겠지만,
문제에서 제시되는 조건에 따르면 행번호가 작은 오른쪽의 승객을 먼저 태워야한다
x,y의 우선순위를 바꾸더라도 택시의 위치에 따라 달라질 수 있으므로
조건문을 활용해서 행, 열의 위치로 먼저 태울 승객을 정하는게 좋을 듯

2. 시간초과

시간초과를 해결하기 위해 생각해봐야 할 것이 있다.
1) 어떤 승객을 태울지 선택하는 과정
A,B,C 라는 승객이 있다고 가정할 때 각각의 승객마다 bfs로 최소거리를 잴 수도 있다
그런데 현재 택시 위치에서 bfs로 가장 먼저 발견하는 승객을 태우는 방법으로 하면 더 빠르게 선택할 수 있다
또한 먼저 발견한 승객의 위치에서 해당 승객까지의 거리를 이용해 바로 태웠을때의 상황으로 넘어갈 수 있다

2) 목적지 까지 도달하기 전 연료 확인하는 방법
A승객을 태우고 도착지까지 가는 과정에서 보유한 연료를 넘는 순간 종료한다
그 이상은 진행해 볼 필요가 없기 때문에

3) 태울 수 있는 승객이 없거나 승객을 목적지에 도달할 수 없는 경우
어느 경우라도 결과는 실패이므로 -1 출력하고 return으로 종료

소스코드

class Solution {
 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static int N;
	private static int M;
	private static int F;
	private static int[][] map;
	static int[][] guests;
	static int guestCnt;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, 1, -1 };
	static Queue<Loc> q = new LinkedList<>();
	static boolean[][] chk;
	static int sx, sy;
	static int minStep;

	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()); // 승객 수
		F = Integer.parseInt(st.nextToken()); // 초기 연료
		map = new int[N][N];
		guestCnt = M;
		// 지도 입력받기
		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());
			}
		}
		guests = new int[M + 2][2];
		// 승객 정보 및 택시 출발점 지정
		st = new StringTokenizer(br.readLine());
		sx = Integer.parseInt(st.nextToken()) - 1; // 택시 시작점
		sy = Integer.parseInt(st.nextToken()) - 1;
		for (int j = 0; j < M; j++) {
			st = new StringTokenizer(br.readLine());
			int sx = Integer.parseInt(st.nextToken()) - 1;
			int sy = Integer.parseInt(st.nextToken()) - 1;
			int ex = Integer.parseInt(st.nextToken()) - 1;
			int ey = Integer.parseInt(st.nextToken()) - 1;
			map[sx][sy] = j + 2; // 승객을 2부터 2+M으로 지도에 표시
			guests[j + 2][0] = ex; // 승객 목적지를 알아내기 위해 쓰는 배열
			guests[j + 2][1] = ey;
		}

		while (guestCnt > 0) {
			int mx = Integer.MAX_VALUE, my = Integer.MAX_VALUE;
			minStep = Integer.MAX_VALUE;
			q.clear();
			chk = new boolean[N][N];
			q.add(new Loc(sx, sy));

			boolean foundGuest = false; // 태울 승객 찾았나요?
			int step = 0;
			while (!q.isEmpty()) {
				int size = q.size();
				for (int s = 0; s < size; s++) { // size만큼 돌면서 step체크
					Loc curr = q.poll();
					if (map[curr.x][curr.y] > 1) { // 해당 위치가 승객이 있는 곳이라면
						if (!foundGuest) {
							mx = curr.x;
							my = curr.y;
							foundGuest = true;
						} else { // 기존 승객과 행, 열 위치 비교
							if (mx > curr.x) {
								mx = curr.x;
								my = curr.y;
							} else if (mx == curr.x && my > curr.y) {
								my = curr.y;
							}
						}
					}
					for (int j = 0; j < 4; j++) {
						int nx = dx[j] + curr.x;
						int ny = dy[j] + curr.y;
						if (isBoundary(nx, ny)) {
							chk[nx][ny] = true;
							q.add(new Loc(nx, ny));
						}
					}
				}
				if (foundGuest) {
					minStep = step;
					break;
				}
				step++;
			}

			if (!foundGuest) { // 태울 승객이 없으므로 종료
				System.out.println(-1);
				return;
			}
			// 승객 태웠으니 목적지까지 델다주자
			F -= minStep;
			int stepsToDest = getDistance(mx, my, guests[map[mx][my]][0], guests[map[mx][my]][1]);
			if (stepsToDest == -1) {
				System.out.println(-1);
				return;
			} else {
				// 승객을 목적지에 성공적으로 데려다 준 경우
				F += stepsToDest; // 연료 충전
				sx = guests[map[mx][my]][0]; // 승객 마지막위치가 시작점
				sy = guests[map[mx][my]][1];
				map[mx][my] = 0; // 승객을 지도에서 제거
				guestCnt--; // 승객 수 감소
			}
		}
		System.out.println(F);
	}

	private static int getDistance(int tx, int ty, int ex, int ey) {
		// tx,ty -> ex,ey
		q.clear();
		chk = new boolean[N][N];
		chk[tx][ty] = true;
		q.add(new Loc(tx, ty));
		int step = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Loc curr = q.poll();
				if (step > F)
					return -1;
				if (curr.x == ex && curr.y == ey) {
					return step;
				}
				for (int j = 0; j < 4; j++) {
					int nx = dx[j] + curr.x;
					int ny = dy[j] + curr.y;
					if (isBoundary(nx, ny)) {
						chk[nx][ny] = true;
						q.add(new Loc(nx, ny));
					}
				}
			}
			step++;
		}

		return -1;
	}

	private static boolean isBoundary(int nx, int ny) {
		// map범위 내에 위치하면서 벽이 아닌지 판단
		if (nx > -1 && ny > -1 && nx < N && ny < N && map[nx][ny] != 1 && !chk[nx][ny])
			return true;
		return false;
	}

}

class Loc {
	int x;
	int y;
	public Loc(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}