# 백준 3055번 탈출

## Solution

import sys
from collections import deque

r, c = map(int, input().split())

graph = [list(input().strip()) for _ in range(r)]
visit = [[False] * c for _ in range(r)]
water_dist = [[0] * c for _ in range(r)]
hedgehog_dist = [[0] * c for _ in range(r)]

move = [(0, -1), (0, 1), (1, 0), (-1, 0)]

def water_bfs():
queue = deque()
# 물이 있는 곳
for i in range(r):
for j in range(c):
if graph[i][j] == '*':
queue.append((i, j))
visit[i][j] = True

while queue:
x, y = queue.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < r and 0 <= ny < c and not visit[nx][ny] and graph[nx][ny] == '.':
visit[nx][ny] = True
queue.append((nx, ny))
water_dist[nx][ny] = water_dist[x][y] + 1

def hedgehog_bfs():
queue = deque()
# 고슴도치 queue에 넣어주기
for i in range(r):
for j in range(c):
# 다시 초기화
visit[i][j] = False
if graph[i][j] == 'S':
queue.append((i, j))
visit[i][j] = True

while queue:
x, y = queue.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy
# 물이 차있는 곳인지 확인할 때 water_dist[nx][ny]==0, 즉 물이 지나가지 않은 지점도 고려해주어야 한다.
if 0 <= nx < r and 0 <= ny < c and not visit[nx][ny] \
and (graph[nx][ny] == '.' or graph[nx][ny] == 'D') \
and (water_dist[nx][ny] == 0 or water_dist[nx][ny] > hedgehog_dist[x][y] + 1):
visit[nx][ny] = True
hedgehog_dist[nx][ny] = hedgehog_dist[x][y] + 1
queue.append((nx, ny))

water_bfs()
hedgehog_bfs()

for i in range(r):
for j in range(c):
if graph[i][j] == 'D':
if hedgehog_dist[i][j] == 0:
print("KAKTUS")
else:
print(hedgehog_dist[i][j])
• 모범 풀이
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
static StringBuilder sb = new StringBuilder();

static int N, M;
static String[] a;
static int[][] dist_water, dist_hedgehog;
static boolean[][] visit;
static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static ArrayList<Integer> group;

static void input() {
N = scan.nextInt();
M = scan.nextInt();
a = new String[N];
for (int i = 0; i < N; i++)
a[i] = scan.nextLine();
visit = new boolean[N][M];
dist_water = new int[N][M];
dist_hedgehog = new int[N][M];
}

// 모든 물들을 시작으로 동시에 BFS 시작!
static void bfs_water() {
// 모든 물의 위치를 Q에 전부 넣어주기!
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dist_water[i][j] = -1;
visit[i][j] = false;
if (a[i].charAt(j) == '*') {
dist_water[i][j] = 0;
visit[i][j] = true;
}
}
}

// BFS 과정 시작
while (!Q.isEmpty()) {
int x = Q.poll();
int y = Q.poll();
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0], ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;  // 지도를 벗어나는 곳으로 가는가?
if (a[nx].charAt(ny) != '.') continue;  // 갈 수 있는 칸인지 확인해야 한다.
if (visit[nx][ny]) continue;  // 이미 방문한 적이 있는 곳인가?
visit[nx][ny] = true;
dist_water[nx][ny] = dist_water[x][y] + 1;
}
}
}

// 고슴도치를 시작으로 동시에 BFS 시작!
static void bfs_hedgehog() {
// 고슴도치 위치를 Q에 넣어주기!
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dist_hedgehog[i][j] = -1;
visit[i][j] = false;
if (a[i].charAt(j) == 'S') {
dist_hedgehog[i][j] = 0;
visit[i][j] = true;
}
}
}

// BFS 과정 시작
while (!Q.isEmpty()) {
int x = Q.poll();
int y = Q.poll();
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0], ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;  // 지도를 벗어나는 곳으로 가는가?
if (a[nx].charAt(ny) != '.' && a[nx].charAt(ny) != 'D') continue;  // 갈 수 있는 칸인지 확인해야 한다.
if (dist_water[nx][ny] != -1 && dist_water[nx][ny] <= dist_hedgehog[x][y] + 1) continue;  // 물에 잠기지는 않는가?
if (visit[nx][ny]) continue;  // 이미 방문한 적이 있는 곳인가?
visit[nx][ny] = true;
dist_hedgehog[nx][ny] = dist_hedgehog[x][y] + 1;
}
}
}

static void pro() {
// 각 칸마다 물에 닿는 시간 계산하기
bfs_water();

// 고슴도치가 물을 피해 탐색할 수 있는 공간 찾기
bfs_hedgehog();

// 탈출구 'D' 에 대한 결과를 통해 정답 출력하기
for (int i=0;i<N;i++){
for (int j=0;j<M;j++){
if (a[i].charAt(j) == 'D'){
if (dist_hedgehog[i][j] == -1) System.out.println("KAKTUS");
else System.out.println(dist_hedgehog[i][j]);
}
}
}
}

public static void main(String[] args) {
input();
pro();
}

StringTokenizer st;

}

public FastReader(String s) throws FileNotFoundException {
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
}