BOJ - 19238 스타트 택시

19238 스타트 택시 : https://www.acmicpc.net/problem/19238

---

Problem

---

Solve

주어진 조건

• N : 활동 영역, M : 목표 승객 수
• 승객을 태우는 우선순위
  • 현재 택시 위치에서 최단거리인 승객
  • 최단거리가 같은 경우
    1. 행이 작은 승객
    2. 행도 같다면 열이 작은 승객
• 연료
  • 택시가 이동할때마다 1씩 감소
  • 승객을 목적지에 데려다 주면 승객을 태우고 소비한 연료의 2배 만큼 충전된다.
  • 택시가 이동할때 연료가 0이 되면 종료
  • 승객을 태우고 목적지에 도착한 순간 연료가 0이 되면 종료되지 않는다.
• 모든 승객을 데려다 주었다면 남은 연료를 반환
• 모든 승객을 데려다 주지못하거나 연료가 바닥나면 -1반환

이번 문제에서 놓친 조건은 최단거리인 회원을 찾는 곳에서 반례를 놓쳤다.
처음 풀이에서는 최단거리 승객을 구할때 상,좌,우,하 순서대로 BFS를 통해 최단거리 승객을 찾았다.
이 방법의 반례는 현재 택시 위치에서 좌,좌,좌에 있는 승객1과 우,우,상에 있는 승객2를 비교했을때 승객2의 행이 더 작기때문에 승객2를 찾아야한다. 하지만 위의 방법으로 찾게 되면 승객1을 최단거리 승객으로 파악하기 때문에 실패한다.

그렇기 때문에 구현했던 BFS에서 같은 이동횟수에 도달한 승객을 저장하는 PriorityQueue 생성하고 한번 이동할때마다 PQ에 저장된 승객들의 좌표를 비교해서 가장 작은 행과 열을 가지는 승객에 대해서 목적지까지 이동하는 방법을 사용하였다.

---

Code

public class 스타트택시 {
	static int N;
	static int M;
	static int[][] map;
	static Client[] clients;
	static Taxi taxi;

	static int[] dy = {-1, 0, 0, 1};
	static int[] dx = {0, -1, 1, 0};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int initOil = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		clients = new Client[M + 1];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				int e = Integer.parseInt(st.nextToken());
                //승객 번호를 1번부터 M까지 map에 작성하기 위해 벽을 -1로 갱신
				if (e == 1)
					e = -1;
				map[i][j] = e;
			}
		}

		st = new StringTokenizer(br.readLine(), " ");
		int taxiY = Integer.parseInt(st.nextToken())-1;
		int taxiX = Integer.parseInt(st.nextToken())-1;
		taxi = new Taxi(taxiY, taxiX, initOil);

		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int startY = Integer.parseInt(st.nextToken())-1;
			int startX = Integer.parseInt(st.nextToken())-1;
			int endY = Integer.parseInt(st.nextToken())-1;
			int endX = Integer.parseInt(st.nextToken())-1;
			clients[i] = new Client(i, startY, startX, endY, endX);
			map[startY][startX] = i;
		}

		int answer = work();
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//택시 운행
	static int work() {
    	//연료가 0이 되거나 모든 손님을 태울때까지 반복
		while (taxi.oil != 0) {
			//손님찾기
			int client = findClient();
            //-1이 반환되면 연료가 떨어졌거나 손님이 남아있지만 더이상의 손님을 찾지 못하는 경우
			if (client == -1)
				return -1;
            //map에 있는 승객 정보 삭제
			map[clients[client].startY][clients[client].startX] = 0;

			//손님 이동시키기
			if(moveClient(client)){
            	//손님을 목적지까지 데려다주었고 모든 승객을 데려다 주었다면 남은 연료 반환
				if(taxi.clientCount == M) return taxi.oil;
			}else{
            	//손님을 목적지까지 이동시키지 못했다면 -1 반환.
				return -1;
			}
		}
		return -1;
	}

	//승객을 목적지까지 이동
	static boolean moveClient(int num) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {taxi.y, taxi.x});

		boolean[][] visit = new boolean[N][N];
		visit[taxi.y][taxi.x] = true;
		Client client = clients[num];

		int move = 0;

		while (!queue.isEmpty()) {
        	//다음 이동에서 탐색할 좌표 개수
			int size = queue.size();

			for (int s = 0; s < size; s++) {
				int[] pos = queue.poll();

				이동한 좌표가 손님의 목적지라면 택시 좌표와 연료, 태운 승객수를 갱신 후 true반환
				if(pos[0] == client.endY && pos[1] == client.endX){
					taxi.y = pos[0];
					taxi.x = pos[1];
					taxi.oil += move*2 - move;
					taxi.clientCount++;
					return true;
				}

				for(int i=0;i<4;i++){
					int ny = pos[0]+dy[i];
					int nx = pos[1]+dx[i];

					if(ny>=0 && nx>=0 && ny<N && nx<N && map[ny][nx] != -1 && !visit[ny][nx]){
						visit[ny][nx] = true;
						queue.offer(new int[]{ny, nx});
					}
				}
			}

			//이번 이동에서 택시 연료보다 더 많이 움직였다면 종료
			if(++move > taxi.oil) return false;
		}
		return false;
	}

	//최단거리 손님 찾기
	static int findClient() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {taxi.y, taxi.x});

		boolean[][] visit = new boolean[N][N];
		visit[taxi.y][taxi.x] = true;

		int move = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
            //이번 이동에서 태운 승객 저장
            //PQ의 첫번째 손님이 최우선순위의 승객
			PriorityQueue<Client> pq = new PriorityQueue<>();

			for (int s = 0; s < size; s++) {
				int[] pos = queue.poll();

				if(map[pos[0]][pos[1]] != 0){
					pq.offer(clients[map[pos[0]][pos[1]]]);
				}

				for (int i = 0; i < 4; i++) {
					int ny = pos[0] + dy[i];
					int nx = pos[1] + dx[i];

					if (ny >= 0 && nx >= 0 && ny < N && nx < N && map[ny][nx] != -1 && !visit[ny][nx]) {

						visit[ny][nx] = true;
						queue.offer(new int[] {ny, nx});
					}
				}
			}

			//이번 이동에서 승객을 태웠다면 최우선순위 승객이 있던 좌표를 택시 좌표로 갱신하고 연료를 갱신하고 손님 번호 반환.
			if(pq.size()>0){
				Client client = pq.poll();
				taxi.y = client.startY;
				taxi.x = client.startX;
				taxi.oil -= move;
				return client.num;
			}

			//태운 손님이 없고 이동한 거리가 연료보다 많다면 종료
			if (++move > taxi.oil) return -1;
		}
		return -1;
	}

	static class Client implements Comparable<Client>{
		int num;
		int startY;
		int startX;
		int endY;
		int endX;

		public Client(int num, int startY, int startX, int endY, int endX) {
			this.num = num;
			this.startY = startY;
			this.startX = startX;
			this.endY = endY;
			this.endX = endX;
		}

		@Override
		public int compareTo(Client o1){
			int answer = this.startY - o1.startY;

			if(answer == 0){
				answer = this.startX - o1.startX;
			}

			return answer;
		}
	}

	static class Taxi {
		int y;
		int x;
		int oil;
		int clientCount;

		public Taxi(int y, int x, int oil) {
			this.y = y;
			this.x = x;
			this.oil = oil;
			this.clientCount = 0;
		}
	}
}

---

Result

반례.. 생각하기..

---

Reference

https://www.acmicpc.net/board/view/58232