[백준 / BOJ] 19238번 : 스타트 택시 - JAVA

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

19238번: 스타트 택시

내가 걸린 예외사항들

문제 자체는 최단 거리를 위해 BFS를 계속 사용하기만 하면 되는데, 생각 못한 예외사항 때문에 계속 틀렸습니다 를 받았다.

 

1. 목적지가 중복될 수 있다.

입력의 제한 사항에는 "모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다."라고만 되어 있기 때문에 각 승객의 출발지는 달라도 목적지는 같을 수 있다.

 

처음에는 N * N 배열을 만들어서 지정된 목적지에 승객 번호를 작성했는데, 이 경우에는 중복 목적지를 나타낼 수 없다. 따라서 M * 2 배열로 변경하고, 각 승객 번호에 목적지를 저장하도록 했다.

int[][] start = new int[N][N];
int[][] end = new int[M + 1][2];

for (int i = 1; i <= M; i++) {
    st = new StringTokenizer(br.readLine());
    int sr = Integer.parseInt(st.nextToken()) - 1;
    int sc = Integer.parseInt(st.nextToken()) - 1;
    int er = Integer.parseInt(st.nextToken()) - 1;
    int ec = Integer.parseInt(st.nextToken()) - 1;

    start[sr][sc] = i;
    end[i][0] = er;
    end[i][1] = ec;
}

2. dr, dc 방향 순서로 우선 순위를 맞출 수 없다.

1) r이 작은 곳 2) c가 작은 곳이니 BFS가 나아가는 방향 순서를 위, 왼쪽, 오른쪽, 아래 로 설정해둔다고 해서 우선 순위에 맞는 값을 얻을 수는 없다. 먼저 나오는 위 -> 왼쪽 -> 아래 보다 나중에 나오는 오른쪽 -> 오른쪽 -> 위 가 더 우선 순위가 높기 때문이다.

 

따라서 승객을 탑승 시킬 때에는 사용 연료에 유의하면서 매번 행과 열을 비교해주어야 한다. 

 

3. 목적지에 도달하지 못하는 경우도 확인한다.

이건 사실 바보같은 실수인데.. 원래는 아래와 같은 코드만 있었다.

if(end[stand][0] == cur[0] && end[stand][1] == cur[1]) {
    if(cur[2] <= bj[2]) {					
        bj[0] = cur[0];
        bj[1] = cur[1];
        bj[2] += cur[2];
        return;
    } else {
        bj[0] = -1;
        return;
    }
}

if(cur[2] > bj[2]) {
    bj[0] = -1;
    return;
}

목적지에 도달하되 연료가 갖고 있는 것과 같거나 작아야 하고, 그렇지 않다면 '불가' 표시를 하고 리턴 시키는 것이다. 아래는 목적지에 도달한 적 없이 갖고 있는 연료보다 많이 써야 하는 경우다.

 

이 때 한 가지 빠진 것이 "연료는 충분히 남았는데 목적지 자체에 도달할 수 없는 경우"이다. 벽에 둘러싸여 있다든가 하는 이유로 접근이 안되는 경우를 빠뜨렸다. 따라서 while문이 끝났는데도 목적지에 도달하지 못한 경우를 추가했다.

if(bj[0] != end[stand][0] || bj[1] != end[stand][1]) {
    bj[0] = -1;
    return;
}

 

전체 코드

// 시간 : 148ms
// 메모리 : 19676KB
public class Main {

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,-1,0,1};
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] bj = new int[3];
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		bj[2] = Integer.parseInt(st.nextToken());
		
		boolean[][] map = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j * 2) == '0' ? true : false;
			}
		}
		
		st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken()) - 1;
		int c = Integer.parseInt(st.nextToken()) - 1;
		
		bj[0] = r;
		bj[1] = c;
		
		int[][] start = new int[N][N];
		int[][] end = new int[M + 1][2];
		
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int sr = Integer.parseInt(st.nextToken()) - 1;
			int sc = Integer.parseInt(st.nextToken()) - 1;
			int er = Integer.parseInt(st.nextToken()) - 1;
			int ec = Integer.parseInt(st.nextToken()) - 1;
			
			start[sr][sc] = i;
			end[i][0] = er;
			end[i][1] = ec;
		}
		
		
		while(M > 0) {
			find_start(start, end, map, bj);
			if(bj[0] == -1) {
				System.out.println(-1);
				return;
			}
			M--;
		}
		
		System.out.println(bj[2]);
	}

	private static void find_start(int[][] start, int[][] end, boolean[][] map, int[] bj) {

		int N = map.length;
		boolean[][] v = new boolean[N][N];
		
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] {bj[0], bj[1], 0});
		v[bj[0]][bj[1]] = true;
		
		int r = -1;
		int c = -1;
		int k = Integer.MAX_VALUE;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			if(cur[2] > bj[2]) continue;
			
			if(start[cur[0]][cur[1]] != 0) {
				if(k > cur[2]) {
					r = cur[0];
					c = cur[1];
					k = cur[2];
				} else if(k == cur[2]) {
					if(r > cur[0]) {
						r = cur[0];
						c = cur[1];
					} else if(r == cur[0]) {
						if(c > cur[1]) {
							c = cur[1];
						}
					}
				}
				continue;
			}
			
			if(cur[2] >= k) continue;
			
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr >= N || nc >= N || nr < 0 || nc < 0 || !map[nr][nc]) continue;
				if(v[nr][nc]) continue;
				
				v[nr][nc] = true;
				que.offer(new int[] {nr, nc, cur[2] + 1});
			}
		}
		
		if(r == -1) {
			bj[0] = -1;
			return;
		}
		
		bj[0] = r;
		bj[1] = c;
		bj[2] -= k;
		if(bj[2] < 0) {
			bj[0] = -1;
			return;
		}
		
		int stand = start[r][c];
		
		start[r][c] = 0;
		
		que = new LinkedList<>();
		que.offer(new int[] {bj[0], bj[1], 0});
		
		v = new boolean[N][N];
		v[bj[0]][bj[1]] = true;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			
			if(end[stand][0] == cur[0] && end[stand][1] == cur[1]) {
				if(cur[2] <= bj[2]) {					
					bj[0] = cur[0];
					bj[1] = cur[1];
					bj[2] += cur[2];
					return;
				} else {
					bj[0] = -1;
					return;
				}
			}
			
			if(cur[2] > bj[2]) {
				bj[0] = -1;
				return;
			}
			
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr >= N || nc >= N || nr < 0 || nc < 0 || !map[nr][nc]) continue;
				if(v[nr][nc]) continue;
				
				v[nr][nc] = true;
				que.offer(new int[] {nr, nc, cur[2] + 1});
			}
		}
		if(bj[0] != end[stand][0] || bj[1] != end[stand][1]) {
			bj[0] = -1;
			return;
		}
	}

	
}