3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
0. 물이 찰 예정인 칸으로 진행할 수 없다 -> 물을 먼저 채우고 고슴도치를 이동시키면 된다
- 고슴도치는 변수로 적절하지 않으니 대신 뜨또를 변수로 사용하였다.
1. 물 한번 - 고슴도치 한번 번갈아가며 빈 칸을 채우는 BFS 실행
- ans가 갱신된 그 순간이 곧 최소시간이므로 즉시 탈출한다
- 끝까지 갱신되지 못했다면 정해진 문자열 출력
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
char[][]map=new char[n+2][m+2];
for (int i = 0; i < m+2; i++) {
map[0][i]='X';
map[n+1][i]='X';
}for (int i = 0; i < n+2; i++) {
map[i][0]='X';
map[i][m+1]='X';
}
Queue<int[]>bieber=new LinkedList<>();
Queue<int[]>water=new LinkedList<>();
for (int i = 1; i < n+1; i++) {
String s = br.readLine();
for (int j = 1; j < m+1; j++) {
map[i][j]=s.charAt(j-1);
if(map[i][j]=='S')bieber.offer(new int[] {i,j});
if(map[i][j]=='*')water.offer(new int[] {i,j});
}
}
int time=0, ans=-1;
while(!bieber.isEmpty()) {
time++;
int len = water.size();
//1. 물부터 진행,
for (int i = 0; i < len; i++) {
int[] cur=water.poll();
for (int j = 0; j < 4; j++) {
int tx=cur[0]+dx[j], ty=cur[1]+dy[j];
if(tx<1||tx>n||ty<1||ty>m)continue;
if(map[tx][ty]=='S'||map[tx][ty]=='.') {
map[tx][ty]='*';
water.offer(new int[] {tx,ty});
}
}
}
//2. 뜨또 진행
len = bieber.size();
for (int i = 0; i < len; i++) {
int[] cur=bieber.poll();
for (int j = 0; j < 4; j++) {
int tx=cur[0]+dx[j], ty=cur[1]+dy[j];
if(tx<1||tx>n||ty<1||ty>m)continue;
if(map[tx][ty]=='.') {
map[tx][ty]='S';
bieber.offer(new int[] {tx,ty});
}
else if(map[tx][ty]=='D') {
ans=time;
}
}
}
if(ans!=-1)break;
}
if(ans==-1)System.out.println("KAKTUS");
else System.out.println(ans);
}
static int[]dx = {1,0,-1,0};
static int[]dy = {0,1,0,-1};
static int pint(String s) {
return Integer.parseInt(s);
}
}
