(Java/자바) - 백준(BOJ) 3055번 : 탈출

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

3055번: 탈출

---

• 문제 : 

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

 

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

 

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

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

 

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

 

 

 

---

• 풀이 :

BFS 문제였습니다.

 

너비 우선으로 1일씩 증가할때마다 물이 차오르고, 물이 차오르는 길을 피해 고슴도치가 전진하는 동작을 구현하면 됩니다.

 

문제를 쉽게 이해하자면 물과 고슴도치가 한 턴씩 번갈아가며 진행하는 땅따먹기를 구현한다고 생각하면 됩니다.

 

 

1. 맵 바깥으로 벗어나는 인덱스 바운드 체크를 하지 않기 위해 board를 R+2, C+2  사이즈로 선언하고 테두리를 벽으로 막음.

 

2. 물이 먼저 차오르기 때문에 물 좌표들의 현재 개수만큼 탐색하며 차오를 수 있는 경우 물로 채우고 다음 이동좌표 후보에 넣음

 

3. 고슴도치가 이동할 수 있는 좌표 후보들을 상, 하, 좌, 우 탐색하며 고슴도치가 이동할 수 있는 칸에 대해 다음 이동좌표 후보에 넣음

 

4. 만약 고슴도치가 D에 도착하면 day 출력, 더이상 이동할 수 없다면 KAKTUS 출력;

 

 

 

 

 

---

• 소스코드 : 

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 int R, C, ax, ay;
	static char[][] board;
	static String input;
	static int[] tmp;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static Queue<int[]> water = new LinkedList<int[]>(); // 물의 위치 후보
	static Queue<int[]> beaver = new LinkedList<int[]>(); // 고슴도치의 위치 후보
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		board = new char[R+2][C+2]; // 맵 바깥으로 벗어나는 경우를 배제하기 위해 테두리를 두름
		for (int i = 1; i <= R; i++) {
			input = br.readLine();
			for (int j = 0; j < C; j++) {
				if(input.charAt(j) == '*') water.add(new int[] {i,j+1});
				if(input.charAt(j) == 'S') beaver.add(new int[] {i,j+1});
				board[i][j+1] = input.charAt(j);
			}
		}
        
        // 테두리 두르기
		Arrays.fill(board[0], 'X');
		Arrays.fill(board[R+1], 'X');
		for (int i = 1; i < R+1; i++) {
			board[i][0] = 'X';
			board[i][C+1] = 'X';
		}
        
        
		int day = 0; // 탈출에 걸리는 일수 
		while(true) {
			day ++;
			int size = water.size(); // 물이 차오르는 좌표들의 길이만큼 반복
			for (int i = 0; i < size; i++) {
				tmp = water.poll(); 
				for (int j = 0; j < 4; j++) { // 상, 하, 좌, 우에 '.'이 있다면 물이 차올라야 하므로 다시 QUEUE에 넣음
					ax = tmp[0] + dx[j];
					ay = tmp[1] + dy[j];
					if(board[ax][ay] != '.') continue;
					board[ax][ay] = '*';
					water.add(new int[] {ax, ay});
				}
			}
			
			// 고슴도치 좌표의 후보들만큼 반복
			size = beaver.size();
			if(size == 0) { // 만약 고슴도치가 더이상 이동할 수 없다면 종료
				System.out.println("KAKTUS");
				return;
			}
            
       
			for (int i = 0; i < size; i++) {
				tmp = beaver.poll();
				for (int j = 0; j < 4; j++) {
					ax = tmp[0] + dx[j];
					ay = tmp[1] + dy[j];
					if (board[ax][ay] == 'D') { // 만약 비버 굴에 도착했을 경우 종료
						System.out.println(day);
						return;
					}
					if(board[ax][ay] != '.') continue; // 물이 차올랐거나 돌로 막혀있는 경우 진행 불가
					board[ax][ay] = 'S'; // 아닐 경우 고슴도치가 갈 수 있는 땅으로 만들고 
					beaver.add(new int[] {ax, ay}); // 고슴도치 이동 좌표 후보에 넣음
				}
			}
			
		}
		
		
	}
	
}