[BaekJoon] 3055 탈출 (Java)

1.  문제 링크

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

2.  문제

요약

• 티떱숲에는 고슴도치가 한 마리 살고 있고 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 합니다.
• 티떱숲의 지도는 R행 C열로 이루어져 있고 비어있는 곳은 '.', 물이 차있는 지역은 '*', 비버의 굴은 'D', 고슴도치의 위치는 'S'로 나타내어져 있습니다.
• 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸(위, 아래, 오른쪽, 왼쪽) 중 하나로 이동할 수 있고 물도 매 분마다 비어있는 칸으로 확장합니다.
• 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 됩니다.
• 물과 도슴고치는 돌을 통과할 수 없고 고슴도치는 물로 차있는 구역으로 이동할 수 없으며 물도 비버의 소굴로 이동할 수 없습니다.
• 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없습니다.
• 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 R, C가 주어지며 두 번째 줄부터 R개의 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어집니다.
  • 'D'와 'S'는 하나씩만 주어집니다.
• 출력: 첫 번째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력하고, 안전하게 굴로 이동할 수 없다면 "KAKTUS"를 출력합니다.

3.  소스코드

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

public class Main {
	static int R, C;
	static char[][] map, water_map;
	static boolean[][] visited, water_visited;
	static Point hedgehog;
	static Queue<Point> water;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static void input() {
		Reader scanner = new Reader();
		R = scanner.nextInt();
		C = scanner.nextInt();
		map = new char[R][C];
		water_map = new char[R][C];
		visited = new boolean[R][C];
		water_visited = new boolean[R][C];
		water = new LinkedList<Point>();
		for(int i = 0; i < R; i++) {
			String info = scanner.nextLine();
			for(int j = 0; j < C; j++) {
				map[i][j] = info.charAt(j);
				if(map[i][j] == 'S') hedgehog = new Point(i, j, 0);
				else if(map[i][j] == '*') {
					water.offer(new Point(i, j, 0));
					water_map[i][j] = '*';
					water_visited[i][j] = true;
				}
			}
 		}
	}
	
	static void solution() {
		Queue<Point> hedgehog_loc = new LinkedList<Point>();
		visited[hedgehog.x][hedgehog.y] = true;
		hedgehog_loc.offer(hedgehog);
		int time = -1;
		while(!hedgehog_loc.isEmpty()) {
			Point cur_point = hedgehog_loc.poll();
			if(map[cur_point.x][cur_point.y] == 'D') {
				System.out.println(cur_point.time);
				return;
			}
			if(cur_point.time > time) {
				extend();
				time++;
			}
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < R && cy >= 0 && cy < C && !visited[cx][cy]) {
					if(water_map[cx][cy] != '*' && map[cx][cy] != 'X') {
						visited[cx][cy] = true;
						hedgehog_loc.offer(new Point(cx, cy, cur_point.time + 1));
					}
				}
			}
		}
		System.out.println("KAKTUS");
	}
	
	static void extend() {
		int cur_time = 0;
		if(!water.isEmpty()) cur_time = water.peek().time;
		while(!water.isEmpty()) {
			Point cur_point;
			if(water.peek().time > cur_time)
				break;
			cur_point = water.poll();
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < R && cy >= 0 && cy < C && !water_visited[cx][cy]) {
					if(map[cx][cy] != 'D' && map[cx][cy] != 'X') {
						water.offer(new Point(cx, cy, cur_time + 1));
						water_map[cx][cy] = '*';
						water_visited[cx][cy] = true;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
	static class Point {
		int x, y, time;
		public Point(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 시간이 지남에 따라 물이 확장되는 곳을 확인하고 물이 확장되지 않는 곳으로 BFS를 통해 고슴도치가 이동할 수 있는 경로를 파악하여 비버의 굴에 도착할 수 있는지 확인하고 그렇다면 그 중 가장 시간이 적게 걸리는 경로를 찾아 그 때의 시간을 출력합니다.
• 필요한 위치들을 저장할 때는 Point 클래스를 통해 저장하게 되는데, 이 클래스는 현재 위치를 나타내는 x, y와 그 위치에 방문하였을 때의 시간을 나타내는 time을 멤버 변수로 갖습니다.
• 고슴도치의 위치는 hedgehog라는 변수에 담고 물의 위치들은 Queue에 담으며 주어진 지도의 정보는 map이라는 2차원 배열에 담습니다.
• 물이 확장되는 것을 확인하기 위해 주어진 지도와 같은 크기로 water_map이라는 2차원 배열을 생성하고 물의 위치만을 기록하여 값을 초기화합니다.
• 또한 물이 확장될 때 이미 물이 확장된 곳인지 확인하기 위해 water_visited라는 2차원 배열을 생성하고 주어진 지도의 정보에서 물의 위치들만 true로 초기화합니다.

solution 함수

• 이 함수에서는 BFS를 통해 고슴도치를 이동시켜보며 고슴도치가 비버의 굴에 도착할 수 있는지, 도착할 수 있다면 그 중 가장 짧은 시간은 얼마인지 구하는 함수입니다.
• 고슴도치의 이동 경로를 저장할 Queue를 생성하고 초기 고슴도치의 위치를 Queue에 넣으며 BFS 탐색 시에 각 위치를 방문하였는지를 나타내는 2차원 배열 visited를 생성하여 초기 고슴도치 위치의 visited 값을 true로 변경합니다.
• 고슴도치가 이동한 시간을 나타내는 변수 time을 생성하고 -1로 초기화합니다.
• Queue가 비워질 때까지 Queue에 있는 각 위치들을 탐색하면서 고슴도치가 비버의 굴에 도착할 수 있는지, 그 중 가장 짧은 시간은 얼마인지 구합니다.
  • Queue에서 현재 탐색하려는 위치를 하나 뽑고 그를 cur_point라는 변수에 담습니다.
  • 만약 탐색하는 위치의 map 값이 D라면, 비버의 굴에 도착했다는 뜻이므로 그 때의 시간을 출력합니다.
  • 만약 현재 탐색하는 위치까지의 시간이 변수 time 값보다 크다면 특정 시간대에 이동할 수 있는 모든 위치들을 탐색했고 1분이 지났다는 의미이므로 물의 확장을 구하고 time 값을 1 늘립니다.
  • 현재 탐색하는 위치의 상하좌우 위치를 보면서 그 위치가 지도 내에 존재하고 아직 방문되지 않았으며 물의 확장 이후 아직 물이 차지 않았고 그 위치가 돌이 아니라면 해당 위치로 이동할 수 있으므로 그 위치의 visited 값을 true로 변경하고 Queue에 해당 위치를 담습니다.
• Queue가 비워질 때까지 최소 시간이 출력되지 않았다면 이는 비버의 굴에 도달할 수 없다는 뜻이므로 "KAKTUS"를 출력합니다.

extend 함수

• 물의 확장을 구현한 함수입니다.
• 물의 위치를 담은 Queue인 water가 비어있지 않다면 확장시킬 물이 존재한다는 뜻이므로 확장시키기 전의 시간값을 cur_time에 저장해놓고 이후에 이를 활용하여 1분 동안의 확장을 구현합니다.
• water가 비워지기 전까지 각 위치를 탐색하면서 물이 확장될 수 있는 곳이라면 물을 확장시킵니다.
  • 만약 현재 탐색하려고 하는 위치의 시간값이 cur_time보다 크다면 특정 시간대에 확장시킬 수 있는 모든 위치들을 탐색했고 1분이 지났다는 의미이므로 확장을 멈춥니다.
  • 현재 탐색하려는 위치를 cur_point에 담습니다.
  • 현재 탐색하는 위치의 상하좌우 위치를 보면서 그 위치가 지도 내에 존재하고 아직 방문되지 않았으며 그 위치가 비버의 굴이 아니고 돌이 아니라면 그 위치는 물이 확장될 수 있는 위치이므로 water에 그 위치를 담고 그 위치의 water_visited 값을 true로 변경하며 물의 확장을 표시하는 water_map에서 그 위치의 값을 '*'로 변경합니다.