문제 이해

배열이 존재한다.
배열은 'D', 'S', *, X, . 으로 구성되어 있다.
'D'는 목적지, 'S'는 출발지이다.

*은 물이 차 있는 지역으로, 1분에 한번씩 상하좌우로 물이 퍼진다.
X는 돌으로써, 물도 도착할 수 없고, 고슴도치도 올 수 없다.
.은 비어 있는 곳으로, 물과 고슴도치 둘 다 올 수 있다.

마지막으로 목적지인 'D'는 물은 도착할 수 없으며, 고슴도치는 목적지이므로 무조건 올 수 있다.

이 때 고슴도치가 D까지 안전하게 올 수 있는 최소 시간을 구하는 문제이다.

• A . * 일 경우(A : 현재 고슴도치 위치) 1분 후에 고슴도치는 .으로 이동할 수 없다. 왜냐하면, 고슴도치가 .으로 이동할 경우, 물도 .에 도착하므로 고슴도치는 물에 빠지기 때문이다.

---

문제 풀이

먼저 고슴도치는 다음 시간에 물이 찰 예정인 칸으로 움직일 수 없다.
이 말인 즉슨, 물을 먼저 퍼뜨린 이후 고슴도치를 이동시켜 보면 자연스럽게 해결될 문제이다.

정확히는 0.5초에 물이 다 퍼지고, 1초에 고슴도치가 움직인다고 생각하면 위의 제한 조건을 별 문제 없이 해결할 수 있을 것이다.

이동에는 가중치가 없으므로, 위 문제는 가중치 없는 그래프에서 최소 거리를 찾는 문제이다.
따라서 BFS를 통해 문제를 해결하였다.

참고로, BFS의 Node에는 (x,y) 좌표와 그 좌표 도달까지 걸린 시간이 주어질 텐데, 현재 Node를 검사하기 이전에 저장된 시간이 time이고, 현재 Node에 저장된 시간이 time + 1이면 BFS의 특징에 따라 더 이상 time 이하의 시간은 생각할 필요가 없어진다. 따라서, 시간값이 바뀔 때 물을 퍼뜨리는 작업을 추가해 줄 필요가 있다.

---

코드

import java.io.*;
import java.util.*;

class Sub{
	int x;
	int y;
	int length;
	public Sub(int x, int y,int length) {
		this.x = x;
		this.y = y;
		this.length = length;
	}
}

public class Main {
	static int N,M;
	static boolean[][] visit; //0 : 안 지났었음, 1: 지났었음
	static int[][] arr; 
    /*
    0 : 비버 & 물 이동 가능 구역, 1 : 물, 2 : 둘 다 못감, 3 : 도착지, 
    4 : 물 찰 예정
    
    4를 따로 표시한 이유 : 이미 물이 찬 구역은 다시 물을 퍼뜨릴 필요가 없다.
    따라서, 이번 시간에 물이 확장되는 좌표는 4로, 이미 물을 확장시켜 더 이상 
    확장 시킬 필요가 없는 좌표는 1로 표기하여 둘을 구분해주었다.
    */
	
	static Queue<Sub> water = new LinkedList<>();
	
	static void water_flow() {
        // 물 확장 메서드
		int size = water.size();
		for(int i =0;i<size;i++) {
			Sub tmp = water.poll();
			
			if(arr[tmp.x][tmp.y]==1) continue;
			arr[tmp.x][tmp.y] = 1;
			
			if(tmp.x>0 && arr[tmp.x-1][tmp.y]==0) {
				water.add(new Sub(tmp.x-1,tmp.y,0));
				arr[tmp.x-1][tmp.y] = 4;
			}
			if(tmp.x+1<N && arr[tmp.x+1][tmp.y]==0) {
				water.add(new Sub(tmp.x+1,tmp.y,0));	
				arr[tmp.x+1][tmp.y] = 4;
			}
			if(tmp.y >0 &&arr[tmp.x][tmp.y-1]==0) {
				water.add(new Sub(tmp.x,tmp.y-1,0));
				arr[tmp.x][tmp.y-1] = 4;
			}
			if(tmp.y+1<M && arr[tmp.x][tmp.y+1]==0) {
				water.add(new Sub(tmp.x,tmp.y+1,0));
				arr[tmp.x][tmp.y+1] = 4;
			}
		}
	}
	
	static Integer dfs(Sub start) {
		Queue<Sub> queue = new LinkedList<>();
		
		queue.add(start);
		water_flow();
		
		int change = start.length;
		while(!queue.isEmpty()) {
			Sub tmp = queue.poll();
			
			if(arr[tmp.x][tmp.y] == -1) return tmp.length;
            // BFS 특징. 처음으로 목적에 도착했으면 그 때의 거리가 최소 거리

			if(visit[tmp.x][tmp.y]) continue; 
            // 이미 방문했던 좌표. 즉 처리했던 좌표이다.
			
			if(change!=tmp.length) {
                // 시간이 바뀌었으므로 물을 먼저 확장시켜준다
				change = tmp.length;
				water_flow();
			}
			
			visit[tmp.x][tmp.y] = true;
			
			if(tmp.x>0 && arr[tmp.x-1][tmp.y]<=0) {
				queue.add(new Sub(tmp.x-1,tmp.y,tmp.length+1));
			}
			if(tmp.x+1<N && arr[tmp.x+1][tmp.y]<=0) {
				queue.add(new Sub(tmp.x+1,tmp.y,tmp.length+1));
			}
			if(tmp.y >0 &&arr[tmp.x][tmp.y-1]<=0) {
				queue.add(new Sub(tmp.x,tmp.y-1,tmp.length+1));
			}
			if(tmp.y+1<M && arr[tmp.x][tmp.y+1]<=0) {
				queue.add(new Sub(tmp.x,tmp.y+1,tmp.length+1));
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N][M];
		visit = new boolean[N][M];
		
		Sub start = null;
		for(int i =0;i<N;i++) {
			String tmp = sc.next();
			for(int j =0;j<M;j++) {
				char c = tmp.charAt(j);
				
				switch(c) {
				case 'S':
					start = new Sub(i,j,0); // 시작점
					break;
				case '*':
					water.add(new Sub(i,j,0)); 
                    // 물의 위치를 미리 모두 저장해 놓았다.
					break;
				case 'D':
					arr[i][j] = -1;
					break;
				case 'X':
					arr[i][j] = 2;
					break;
				}
			}
		}
		
		int ans = dfs(start);
		if(ans==-1) System.out.println("KAKTUS"); 
        // 목적지에 도착할 수 없는 경우
		else System.out.println(ans);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과