BOJ 3055번: 탈출

문제

문제 바로가기> BOJ 3055번: 탈출

3055번: 탈출

 

풀이

BFS를 이용하여 문제를 해결했다.

물이 매 분마다 비어있는 칸으로 확장하고,

다음 시간에 물이 찰 예정인 칸으로 고슴도치가 이동할 수 없으므로

고슴도치의 이동 전에, 물의 확장을 먼저 처리해주었다.

(분이 바뀔 때 마다 처리해주기 위해서 now 변수를 이용)

 

import java.io.*;
import java.util.*;

public class Main {
	
	static final int[] dy = {-1, 1, 0, 0};
	static final int[] dx = {0, 0, -1, 1};
	
	static int N, M;
	static char[][] map;
	static boolean[][] visited, waterArea;
	
	private static String solution(ArrayDeque<int[]> goseum, ArrayDeque<int[]> water) { // 안전 지역에 도달하는 최소 시간
		int now = 1;
		while(!goseum.isEmpty()) {
			int y = goseum.peek()[0]; // y 좌표
			int x = goseum.peek()[1]; // x 좌표
			int s = goseum.peek()[2]; // 시간
			goseum.poll();
			if(map[y][x] == 'D') return s+""; // 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간
			
			if(s==now) { // 물도 매 분마다 비어있는 칸으로 확장
				now++;
				int size = water.size();
				while(size-->0) {
					int r = water.peek()[0];
					int c = water.peek()[1];
					water.poll();
					for(int d=0; d<4; d++) {
						int nr=r+dy[d];
						int nc=c+dx[d];
						if(nr<0 || nr>=N || nc<0 || nc>=M) continue;
						if(map[nr][nc]=='X' || waterArea[nr][nc] || map[nr][nc] == 'D') continue;
						waterArea[nr][nc] = true;
						water.offer(new int[] {nr, nc});
					}
				}
			}
			
			for(int d=0; d<4; d++) { // 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동
				int ny=y+dy[d];
				int nx=x+dx[d];
				if(ny<0 || ny>=N || nx<0 || nx>=M || waterArea[y][x]) continue;
				if(visited[ny][nx] || waterArea[ny][nx] || map[ny][nx]=='X') continue;
				visited[ny][nx] = true;
				goseum.offer(new int[] {ny,nx,s+1});
			}
		}
		return "KAKTUS";
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		visited = new boolean[N][M];
		waterArea = new boolean[N][M];
		ArrayDeque<int[]> goseum = new ArrayDeque<>();
		ArrayDeque<int[]> water = new ArrayDeque<>();
		
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = line.charAt(j);
				if(map[i][j] == 'S') { // 고슴도치의 위치
					map[i][j] = '.';
					visited[i][j] = true;
					goseum.offer(new int[] {i, j, 0});
				}
				if(map[i][j] == '*') { // 물이 차있는 지역
					waterArea[i][j] = true;
					water.offer(new int[] {i, j});
				}
			}
		}
		System.out.println(solution(goseum, water));
		br.close();
	}
}