✨ 문제

백준 3055 탈출

🎈 접근 방식

1. 고슴도치가 상하좌우 4가지로 움직이고 BFS를 활용하여 풀 수 있다고 생각되었다.
2. 이때, 움직일 수 있는 조건 중 물이 퍼질 것으로 예상되는 좌표는 갈 수 없기에 물을 먼저 BFS로 퍼트려주고 고슴도치를 이동시키기로 한다.
3. 물에 대한 BFS와 고슴도치에 대한 BFS를 각각 다루기 위해 visited도 따로 필요하다고 생각되었고, 처음에 해당하는 좌표들을 큐에 담도록 하였다.

BFS를 따로 해주긴 하는데, 사이즈가 계속 변하기 때문에 전형적인 BFS처럼 while문을 바로 사용하지 않고 큐의 사이즈를 미리 고정으로 꺼내놓고 bfs를 for문 안에서 실행하도록 하였다.

😫 실수한 점이나 놓친 점

bfs를 사용하다보니 최대한 꼼꼼하게 문제를 풀어보려고 노력하였다. 그럼에도, 고슴도치 bfs를 실행하기전에 먼저 size를 가져와서 for안에서 구현했어야했는데 그렇게 안하다보니 고슴도치가 움직여야 할 좌표에 물이 있게 되는 문제가 발생해서 테케가 맞았음에도 계속 정답이 아니라고 나왔다.. 아래는 틀린점을 찾기 위해 이용한 반례입니다.
/
5 5
D...
..XXX
.....
.....
.S...

정답) 5
내 코드 제출) KAKTUS
*/

💻 풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int r, c, min = Integer.MAX_VALUE;
	static int sx, sy, ex, ey; // 출발점, 도착점
	static char[][] map;
	static Queue<int[]> water = new ArrayDeque<>();
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static boolean[][] water_visited;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new char[r][c];
		water_visited = new boolean[r][c];
		
		for (int i = 0; i < r; i++) {
			char[] charArray = br.readLine().toCharArray();
			map[i] = charArray;
			for (int j = 0; j < c; j++) {
				if (charArray[j] == 'S') { // 시작점
					sx = i;
					sy = j;
				}
				if (charArray[j] == 'D') { // 도착점
					ex = i;
					ey = j;
				}
				if (charArray[j] == '*') { // 물이 차있는 지역은 따로 관리
					water_visited[i][j] = true; // 먼저 그냥 방문처리 해주고
					water.add(new int[] {i, j});
				}
			}
		}
		
		bfs();
		
		if(min == Integer.MAX_VALUE) {
			System.out.println("KAKTUS");
		} else {
			System.out.println(min);
		}
		
	}
	
	static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>(); // 고슴도치 좌표
		boolean[][] visited = new boolean[r][c]; // 고슴도치의 방문을 확인하기 위해
		queue.offer(new int[] {sx, sy, 0}); // x, y 좌표와 이동거리
		visited[sx][sy] = true;
		
		while (!queue.isEmpty()) {
			int wq_size = water.size();
			// 물의 좌표를 가져와서 먼저 전부 확산 시켜주고
			for(int k = 0; k < wq_size; k++) {
				int[] cur_water = water.poll();
				int c_x = cur_water[0];
				int c_y = cur_water[1];
				for (int i = 0; i < 4; i++) {
					int nc_x = c_x + dx[i];
					int nc_y = c_y + dy[i];
					if (nc_x < 0 || nc_x >= r || nc_y < 0 || nc_y >= c) { // 범위를 벗어난다면
						continue;
					}
					if (map[nc_x][nc_y] == 'X' || map[nc_x][nc_y] == 'D' || map[nc_x][nc_y] == 'S') {
						continue;
					}
					if (!water_visited[nc_x][nc_y]) {
						water_visited[nc_x][nc_y] = true;
						map[nc_x][nc_y] = '*';
						water.offer(new int[] {nc_x, nc_y});			
					}
				}
			}
			int q_size = queue.size();
			
			for (int k = 0; k < q_size; k++) {
				int[] cur = queue.poll();
				if (cur[0] == ex && cur[1] == ey) {
					min = Math.min(min, cur[2]);
				}
				// 이제 고슴도치를 이동
				for (int i = 0; i < 4; i++) {
					int nx = cur[0] + dx[i];
					int ny = cur[1] + dy[i];
					if (nx < 0 || nx >= r || ny < 0 || ny >= c) { // 범위를 벗어난다면
						continue;
					}
					if (map[nx][ny] == 'X' || map[nx][ny] == '*') {
						continue;
					}
					if (!visited[nx][ny]) {
						visited[nx][ny] = true;
						map[nx][ny] = 'S';
						queue.offer(new int[] {nx, ny, cur[2] + 1});
					}
				}	
			}
		}
	}
}