[백준] 3055 탈출

문제 출처: www.acmicpc.net/problem/3055

3055번: 탈출

: 고슴도치는 사방으로 움직일 수 있고, 물은 사방으로 확장될 수 있다.

: 이때, 고슴도치는 비버의 굴로 도망가서 홍수를 피해야 한다.

: 고슴도치가 홍수를 피할 수 있다면 피하는데 걸리는 가장 빠른 시간을 출력하고, 이동할 수 없다면 "KAKTUS"를 출력해야 한다.

: 고슴도치와 물을 동시에 옮겨주어야 하기 때문에 하나의 while문 안에서 BFS 방식으로 이동과 확장을 시켜준다.

: 만약 고슴도치가 while문을 끝내고 나오게 될 경우 비버의 숲에 도착할 수 없었다는 것이므로, KAKTUS를 출력하낟.

: while문 안에서 비버의 굴 좌표에 도착하게 되면 그 때까지 걸렸던 시간을 바로 return 시켜서 도착했음을 알린다. 

 

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

public class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int R, C;
	static char[][] map;
	static Queue<Point> sq = new LinkedList<>();
	static Queue<Point> wq = new LinkedList<>();
	static class Point{
		int r, c, cnt;

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + ", cnt=" + cnt + "]";
		}
		
		
	}
	static Point dest;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new char[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] == 'S')sq.add(new Point(i, j, 0));
				if(map[i][j] == '*')wq.add(new Point(i, j, 0));
				if(map[i][j] == 'D')dest = new Point(i, j);
			}
		}
		int res = bfs();

		if(res == -1) System.out.println("KAKTUS");
		else System.out.println(res);
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	private static int bfs() {
		int res = -1;
		while(!sq.isEmpty()) {
			int ssize = sq.size();
			int wsize = wq.size();

			for(int i = 0; i < wsize; i++) {
				Point cur = wq.poll();
				for(int j = 0; j < 4; j++) {
					int nr = cur.r + dr[j];
					int nc = cur.c + dc[j];

					if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
					if(map[nr][nc] == '*' || map[nr][nc] == 'S' || map[nr][nc] == 'D' || map[nr][nc] == 'X') continue;
					map[nr][nc] = '*';
					wq.add(new Point(nr, nc));					
				}
			}
			for(int i = 0; i < ssize; i++ ) {
				
				Point cur = sq.poll();
				for(int j = 0; j < 4; j++) {
					
					int nr = cur.r + dr[j];
					int nc = cur.c + dc[j];
					if(nr == dest.r && nc == dest.c) {
						res = cur.cnt+1;
						return res;
					}
					if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
					if(map[nr][nc] == '*' || map[nr][nc] == 'S' || map[nr][nc] == 'X') continue;
					map[nr][nc] = 'S';
					sq.add(new Point(nr, nc, cur.cnt+1));
				}
			}
		}
		return res;
	}
}