[백준] G4 19238 스타트 택시 (자바)

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

19238번: 스타트 택시

 

풀이

 

1) bfs로 승객을 찾는다. 이때 PrioritiQueue를 써서 우선순위가 높은 순서대로 뽑아야 한다.

2) 승객을 찾을때 생긴 비용을 총 연료에서 뺀다. 이때 연료가 바닥나면 실패.

3) 승객을 찾고도 연료가 바닥나지 않으면 해당 승객의 번호에 맞는 도착지를 찾는다. 

4) 도착지를 찾을때 생긴 비용을 총 연료에서 뺀다. 이때 연료가 0 이하면 실패.

5) 도착지를 찾고도 연료가 0이상이면 4)에서 생긴 비용 * 2 를 더한다.

6) 다 돌고 못탄 승객 or 남은 도착지가 있을경우 -1을 출력, 그렇지 않으면 남은 연료 출력.

 

주의사항

 

1. 승객을 태우는 순서 : 거리 > 행 > 열
2. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다. <- 목적지는 겹칠 수 있다.

 

package com.baekJoon;

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

public class BJ_G4_19238_스타트택시 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,fuel, passanger[][], taxiR,taxiC,cur,plus;
	static boolean isVisited[][];
	static List<Node> dest = new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		fuel = Integer.parseInt(tokens.nextToken());
		passanger = new int[N][N];
		isVisited = new boolean[N][N];
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				int map = Integer.parseInt(tokens.nextToken());
				passanger[r][c] = map;
			}	
		}
		tokens = new StringTokenizer(input.readLine());
		taxiR = Integer.parseInt(tokens.nextToken())-1;
		taxiC = Integer.parseInt(tokens.nextToken())-1;
		int cnt = 2;
		for(int m=0; m<M; m++) {
			tokens = new StringTokenizer(input.readLine());
			int pr = Integer.parseInt(tokens.nextToken())-1;
			int pc = Integer.parseInt(tokens.nextToken())-1;
			int dr = Integer.parseInt(tokens.nextToken())-1;
			int dc = Integer.parseInt(tokens.nextToken())-1;
			passanger[pr][pc] = cnt; 
			dest.add(new Node(dr, dc, cnt++));
		} // 입력 끝

		boolean isFailed = false;
		for(int m=0; m<M; m++) {
			findPass(); // 가장 가까운 승객 찾기
			if(fuel<=0) {
				isFailed = true;
				break;
			}
			passanger[taxiR][taxiC] = 0; // 해당 승객은 이제 제외함.
			
			findDest(cur); // cur = 승객 번호이자 도착번호
			if(fuel<0) { // 0은 봐줌
				isFailed = true;
				break; 
			}
			fuel += plus;
			plus = 0;
		}
		
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				if(passanger[r][c] > 1) { // 승객이 남은 경우 실패이다.
					isFailed = true;
					break;
				}
			}	
		}
		if(isFailed || dest.size() > 0) { // 목적지가 남아도 실패이다.
			System.out.println(-1);
		}else {
			System.out.println(fuel);
		}
	}
	
	private static void findPass() { // 가까운 승객 찾기
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				isVisited[r][c] = false;
			}	
		}
		PriorityQueue<Node> queue = new PriorityQueue<>();
//		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(taxiR, taxiC, 0));
		isVisited[taxiR][taxiC] = true;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			if(passanger[front.r][front.c] > 1) { // 만약 승객을 발견하면
				taxiR = front.r; // 택시 위치 초기화
				taxiC = front.c; 
				fuel -= front.d; // 연료 감소
				cur = passanger[front.r][front.c];
				break;
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && passanger[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.d+1));
				}
			}
		}
	}
	
	private static void findDest(int cur) { // cur 승객의 목적지 찾기
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				isVisited[r][c] = false;
			}	
		}
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(taxiR, taxiC, 0));
		isVisited[taxiR][taxiC] = true;
		
		outer : while(!queue.isEmpty()) {
			Node front = queue.poll();
			for(int i=0; i<dest.size(); i++) {
				if(front.r == dest.get(i).r && front.c == dest.get(i).c && dest.get(i).d == cur) {
					taxiR = front.r;
					taxiC = front.c;
					fuel -= front.d;
					plus = front.d * 2;
					dest.remove(i); // 해당 목적지는 삭제.
					break outer;
				}
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && passanger[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc, front.d+1));
				}
			}
		}
		
	}
	
	
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<N && c<N);
	}
	static int dr[] = {-1,0,0,1}; // 상,좌,우,하 <- 순서 중요
	static int dc[] = {0,-1,1,0};
	static class Node implements Comparable<Node>{
		int r;
		int c;
		int d;
		public Node(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
		@Override
		public int compareTo(Node o) {
			if(this.d == o.d) {
				if(this.r == o.r) {
					return Integer.compare(this.c, o.c);
				}
				return Integer.compare(this.r, o.r);
			}
			return Integer.compare(this.d, o.d);
		}
	}
	static String src =
			"6 3 2\r\n" + 
			"0 0 1 0 0 0\r\n" + 
			"0 0 1 0 0 0\r\n" + 
			"0 0 0 1 0 0\r\n" + 
			"0 0 0 1 0 0\r\n" + 
			"0 0 0 0 1 0\r\n" + 
			"0 0 0 1 0 0\r\n" + 
			"1 1\r\n" + 
			"1 1 1 2\r\n" + 
			"1 2 2 2\r\n" + 
			"2 2 2 3"; 
}

 

후기

 

정말 정말 정말 힘들게 풀었다. 예외 상황 뿐만이 아니라 내가 당연하다고 생각했던 상식적인 부분에서 오류가 있어서 그 오류를 발견하기가 정말 힘들었다. 무엇보다도 게시판의 모든 반례에 다 통과가 되어서 무엇이 잘못되었는지 파악할 수가 없었다.

위의 그림은 내가 처음에 bfs의 4방 탐색을 [상-좌-우-하] 의 순서로 할 경우 우선순위를 번호로 매긴것이다.

그림에서 보다시피 9번과 10번, 또 19번과 20번의 우선순위가 맞지 않다. Comparable 안쓰려고 잔머리 굴리다가 크게 당했다.. 생각해보면 당연한건데 왜 이게 될거라고 생각했는지 모르겠다..

아직 더 많은 경험이 필요하다..