[백준 / BOJ] 3055번 : 탈출 - JAVA

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

3055번: 탈출

물과 고슴도치의 순서

문제 조건 중에 이해하기 어려웠던 부분이 있었다.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

이 부분인데, 물이 차오름과 동시에 고슴도치가 이동하니, 그 다음턴까지 파악을 해야 하나 하는 생각이 들었었다. 하지만 결국 정답은 물을 먼저 채우고, 그 다음 고슴도치를 이동시키면 된다.

 

문제에서 몇 번째 턴인지가 중요하기 때문에, 물이 차오르는 위치를 표시할 큐와, 고슴도치의 위치를 표시할 큐 모두에 시간을 같이 넣어주었다. 그리고 턴을 나타내는 time 변수와 cur[2] 값이 같을 때에만 poll할 수 있도록 했다.

 

방문 체크

처음에는 방문 체크 배열 v를 사용하지 않으려고 했다. 물이 차오름에 따라 이동 경로가 바뀔 수 있다고 생각했기 때문이다.하지만 문제를 풀면서 깨달은 게, i 번째에 (r, c)에 처음으로 도착했다면, 그 때가 (r, c)에서 움직일 수 있는 경로가 가장 많은 시점이라는 것이다. 즉, i 번째 이후에 (r, c)에 도착한다면, 물이 계속 차오르고 있기 때문에 기존에 가능했던 이동 방향보다  가능한 경우가 적어질 수 있다. 그리고 한 번에 한 칸 씩만 이동할 수 있기 때문에 방문 체크를 해도 무방하다.

 

"KAKTUS"

while문을 돌다가 고슴도치가 D에 도착하는 순간 return하도록 했기 때문에, while문을 빠져나갈 조건이 따로 필요했다. 따라서 고슴도치가 움직일 수 있는 경로 큐인 kaktus에 더이상 원소가 없는 경우 while문을 끝내도록 했다. 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 시간 : 84ms
// 메모리 : 11896KB
public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		char[][] map = new char[R][C];
		Queue<int[]> que = new LinkedList<>();
        Queue<int[]> kaktus = new LinkedList<>();
        boolean[][] v = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == '*') que.offer(new int[] {i, j, 0});
				else if(map[i][j] == 'S') {
					map[i][j] = '.';
                    kaktus.offer(new int[] {i, j, 0});
                    v[i][j] = true;
				}
			}
		}
		
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		int time = 0;
		
		while(!kaktus.isEmpty()) {
			// 물
			while(!que.isEmpty() && que.peek()[2] == time) {
				int[] cur = que.poll();
				
				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d];
					int nc = cur[1] + dc[d];
					
					if(nr >= R || nc >= C || nr < 0 || nc < 0) continue;
					if(map[nr][nc] != '.') continue;
					map[nr][nc] = '*';
					que.offer(new int[] {nr, nc, cur[2] + 1});
				}
			}
			
			while(!kaktus.isEmpty() && kaktus.peek()[2] == time) {
				int[] cur = kaktus.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d];
					int nc = cur[1] + dc[d];
					
					if(nr >= R || nc >= C || nr < 0 || nc < 0) continue;
					if(v[nr][nc]) continue;
					if(map[nr][nc] == '*' || map[nr][nc] == 'X') continue;
					if(map[nr][nc] == 'D') {
						System.out.println(time + 1);
						return;
					}
					v[nr][nc] = true;
					kaktus.offer(new int[] {nr, nc, cur[2] + 1});
				}
			}
			time++;
		}
		System.out.println("KAKTUS");
	}

}