[BOJ] 3055 : 탈출 [G4]

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

3055번: 탈출

 

 

[문제]

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

[입력]

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

[출력]

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

 

[예제 입력 1]

3 3
D.*
...
.S.

[예제 출력 1]

3

 

[예제 입력 2]

3 3
D.*
...
..S

[예제 출력 2]

KAKTUS

 

 

[내 풀이]

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

/*
	문제 : [G4] 탈출 - 3055번
	성능 요약 : 메모리 15224KB, 시간 144ms
	아이디어 : 
		1. 반복횟수마다 고슴도치와 물 각각 이동할 수 있는지 없는지 판단
		2. 이동할 수 있는 고슴도치(또는 물)이 있을 경우 각각 큐에 담아서
		3. 큐에 담겨진 모든 고슴도치(또는 물)에 대해 이동
		4. 이동하려는 구역이 고슴도치는 '.'일 경우만
		5. 물은 '.', 'S' 일 경우 이동가능하게하여
		6. 돌인 'X'는 고려하지 않아도 되도록 하였습니다.
*/

public class Main {

	static int R, C, ans;
	static boolean isArrive;
	// 이미 검사한 고슴도치인지 체크하기 위한 배열
	static boolean[][] visitedGosum;
	// 이미 검사한 물인지 체크하기 위한 배열
	static boolean[][] visitedWater;
	static Character[][] map;
	static int[][] dxdy = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<int[]> qGosum = new ArrayDeque<>();
	static Queue<int[]> qWater = new ArrayDeque<>();
	
	
	static void checkPath(int del, int row, int col) {
		for (int i=0; i<4; i++) {
			int dx = row + dxdy[i][0];
			int dy = col + dxdy[i][1];
			
			if (dx >= 0 && dx < R && dy >= 0 && dy < C) {
				// 물 (delimiter == 1)
				if (del == 1 && (map[dx][dy] == '.' || map[dx][dy] == 'S')) {
					map[dx][dy] = '*';
				}
				
				// 고슴도치 (delimiter == 2)
				else if (del == 2) {
					// 집 도착
					if (map[dx][dy] == 'D') {
						isArrive = true;
						return;
					}
					else if (map[dx][dy] == '.') {
						map[dx][dy] = 'S';	
					}
				}
			}
		}

	}
	

	static void lookingHome(int count) {
		
		// 고슴도치가 이동할 수 있는지 판별하기 위한 변수
		boolean isfail = true;
		
		// 고슴도치 먼저 이동
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {				
				if (visitedGosum[i][j] == false && map[i][j] == 'S') {
					visitedGosum[i][j] = true;
					isfail = false;
					// 모든 고슴도치 좌표 큐에 담음
					qGosum.offer(new int[] {i, j});
				}
			}
		}
		
		// 검사 안한 고슴도치에 대해 이동할 수 있는지 검사
		while(!qGosum.isEmpty()) {
			int[] temp = qGosum.poll();
			int r = temp[0];
			int c = temp[1];
			checkPath(2, r, c);
		}
		
		// 물로 덮음
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {
				if (visitedWater[i][j] == false && map[i][j] == '*') {
					visitedWater[i][j] = true;
					// 모든 물 좌표 큐에 담음
					qWater.offer(new int[] {i, j});
				}
			}
		}
		
		// 검사 안한 물에 대해 이동할 수 있는지 검사
		while(!qWater.isEmpty()) {
			int[] temp = qWater.poll();
			int r = temp[0];
			int c = temp[1];
			checkPath(1, r, c);
		}
		
		// 고슴도치가 도착지점에 도착했다면 
		if (isArrive) {
			ans = count;
			return;
		}
		// 고슴도치가 더이상 이동할 수 없다면
		else if(isfail) return;
		// 도착지점에 도착하지도 않고 더 이동할 수 있다면 다시 반복(재귀)
		else lookingHome(count + 1);
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new Character[R][C];
		visitedWater = new boolean[R][C];
		visitedGosum = new boolean[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);
			}
		}
		
		lookingHome(1);
		
		// 도착했다면 답 출력, 그렇지 않다면 "KAKTUS" 출력
		if (isArrive) System.out.println(ans);
		else System.out.println("KAKTUS");
	}

}