<백준> 3055번 탈출

<링크>

https://www.acmicpc.net/problem/3055

 

 

<문제>

• 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
• 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
• 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
• 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
• 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

<입력>

• 첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
• 다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

<출력>

• 첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

 

<아이디어>

1. BFS..?
2. 근데 이제 구현을 겸비한..!

<풀이 - JAVA>

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

public class Main {

	// 방향 탐색
	public static final int[] dx = { 1, 0, -1, 0 };
	public static final int[] dy = { 0, 1, 0, -1 };

	// 행, 열 개수
	private static int R, C;

	// 데이터 담자
	private static String[][] map;

	// 방문 체크
	private static boolean[][] visited;

	// D : 비버 굴
	public static int endX, endY;

	// S ; 고슴도치 위치
	public static int startX, startY;

	// 물 위치
	private static Queue<int[]> water = new ArrayDeque<int[]>();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] split = in.readLine().split(" ");
		R = Integer.parseInt(split[0]);
		C = Integer.parseInt(split[1]);

		map = new String[R][C];
		visited = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			split = in.readLine().split("");
			for (int j = 0; j < C; j++) {
				map[i][j] = split[j];
				if (split[j].equals("D")) {
					// 동굴의 위치
					endX = i;
					endY = j;
				}
				if (split[j].equals("S")) {
					// 비버의 위치
					startX = i;
					startY = j;
				}
				if (split[j].equals("*")) {
					// *이면 물의 좌표를 담아놓기.
					water.add(new int[] { i, j });
				}
			}
		}
		
		int result = bfs(startX, startY);
		if (result == -1) {
			System.out.println("KAKTUS");
		} else {
			System.out.println(result);
		}
	}

	private static int bfs(int i, int j) {
		// 몇번만에 갈수있는가?
		int time = 0;
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { i, j });
		visited[i][j] = true;
		while (!queue.isEmpty()) {
			int size = queue.size();
			// 비버가 움직이기 전에 물부터 퍼트려 보아요.
			water();
			for (int s = 0; s < size; s++) {
				int[] current = queue.poll();
				int ex = current[0];
				int ey = current[1];
				if (ex == endX && ey == endY) {
					return time;
				}

				for (int k = 0; k < 4; k++) {
					int nx = ex + dx[k];
					int ny = ey + dy[k];
					if (isVaild(nx, ny) && !visited[nx][ny] && map[nx][ny].equals(".")) {
						visited[nx][ny] = true;
						queue.add(new int[] { nx, ny });
					}
					// 도착했으면 지금까지 움직인 횟수 + 1을 해주기
					if (isVaild(nx, ny) && !visited[nx][ny] && map[nx][ny].equals("D")) {
						return time + 1;
					}
				}
			}
			time++;
		}
		return -1;
	}

	private static void water() {
		int size = water.size();
		for (int s = 0; s < size; s++) {
			int[] current = water.poll();
			int wx = current[0];
			int wy = current[1];

			for (int k = 0; k < 4; k++) {
				int nx = wx + dx[k];
				int ny = wy + dy[k];

				// .인 지역인 곳 즉, 퍼트릴수 있는 위치라면 퍼트려야지?
				if (isVaild(nx, ny) && map[nx][ny].equals(".")) {
					map[nx][ny] = "*";
					water.add(new int[] { nx, ny });

				}
			}
		}
	}

	private static boolean isVaild(int i, int j) {
		return i >= 0 && i < R && j >= 0 && j < C;
	}

}