[백준_3055번] 탈출

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

3055번: 탈출

[문제]

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

 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다. 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

class point_3055 {
	int x,y;
	
	public point_3055(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_3055 {
	static char[][] map;
	static int r,c;
	static int[] dx={-1,0,1,0};
	static int[] dy={0,-1,0,1};
	static Queue<point_3055> water=new LinkedList<>();
	static Queue<point_3055> beaver=new LinkedList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		r=sc.nextInt();
		c=sc.nextInt();
		map=new char[r][c];
	
		for(int i=0;i<r;i++) {
			char[] input=sc.next().toCharArray();
			for(int j=0;j<c;j++) {
				map[i][j]=input[j];
				
				// 물의 좌표를 큐에 삽입
				if(map[i][j]=='*')
					water.add(new point_3055(i,j));
				
				// 비버의 좌푤를 큐에 삽입
				if(map[i][j]=='S')
					beaver.add(new point_3055(i,j));
			}
		}
		
		int time=0;
		while(true) {
			time++; // 시간 증가
			
			/*
			 * 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에
			 * 물을 먼저 이동시키고 난 뒤에 고슴도치를 이동해야 한다. 
			 */
			move_water();
			if(move_beaver()) {
				System.out.println(time); // 비버의 굴에 갈 수 있다면 소요시간 출력
				return;
			}
			
			/*
			 * 고슴도치의 위치가 담긴 큐가 비었다는 것은 
			 * 더 이상 고슴도치가 이동할 수 없다는 의미이므로 KAKTUS 출력
			 * 
			 */
			if(beaver.size()==0) {
				System.out.println("KAKTUS");;
				return;
			}
			
		}
	}
	
	// 물이 상,하,좌,우로 이동하는 함수
	static void move_water() {
		int size=water.size();
		for(int i=0;i<size;i++) {
			point_3055 point=water.poll();
			
			for(int j=0;j<4;j++) {
				int nx=point.x+dx[j];
				int ny=point.y+dy[j];
				
				// 배열 범위 이내이며, 비어있는 곳이라면
				if(nx>=0&&ny>=0&&nx<r&&ny<c) {
					if(map[nx][ny]=='.') {
						map[nx][ny]='*'; // 물로 변경
						water.add(new point_3055(nx,ny)); // 새로운 물의 위치 큐에 삽입
					}
				}
			}
		}
	}
	
	// 비버가 움직이는 함수
	static boolean move_beaver() {
		int size=beaver.size();
		for(int i=0;i<size;i++) {
			point_3055 point=beaver.poll();
			
			// 상,하,좌,우 탐색
			for(int j=0;j<4;j++) {
				int nx=point.x+dx[j];
				int ny=point.y+dy[j];
				
				// 배열의 범위 이내이며
				if(nx>=0&&ny>=0&&nx<r&&ny<c) {
					if(map[nx][ny]=='D') { // 이동한 좌표가 비버의 굴이라면 종료
						return true;
					}
					
					// 이동한 좌표가 비어있는 곳이라면
					if(map[nx][ny]=='.') {
						map[nx][ny]='S'; // 배열 값을 고슴도치의 위치를 나타내는 S로 변경
						beaver.add(new point_3055(nx,ny)); // 새로운 고슴도치 위치 큐에 삽입
					}
				}
			}
		}
		return false;
	}
}

 

[고찰]

 이번 문제는 BFS 알고리즘을 사용하여 해결해야 하는 문제였다. 문제가 길고 복잡하기 구조화를 먼저 해보았다. 

 

0) 물과 고슴도치의 위치를 저장할 2개의 큐 선언, x 좌표와 y 좌표를 저장할 클래스 

 

1) 맵의 정보를 입력 받으면서 초기 물의 좌표와, 고슴도치의 좌표를 각각의 큐에 저장한다.

 

*** 2) 물 이동

2-1) 물의 좌표가 담겨있는 큐에서 하나씩 꺼내며 상, 하, 좌, 우를 탐색한다.

2-2) 탐색한 좌표가 배열 범위 내에 있고, 비어있는 땅이라면 물로 채우고(배열 값을 *로 변경), 큐에 새로운 물의 좌표를 삽입한다.

 

*** 3) 고슴도치 이동

3-1) 고슴도치의 좌표가 담겨있는 큐에서 좌표를 꺼내 상, 하, 좌, 우를 탐색한다.

3-2) 이동한 좌표가 범위 이내이며, 비어있는 땅이라면 고슴도치를 이동시키고(배열의 값을 S로 변경), 큐에 새로운 고슴도치의 좌표를 삽입한다.  

3-3) 이동한 좌표가 범위 이내이며, 배열 값이 비버의 굴(배열 값 : D)이라면 함수를 종료시킨다.

 

이렇게 구조화를 시킨 후 하나씩 구현하면 복잡하긴 하지만 풀어낼 수 있었다. 문제가 길고 어려울 때는 이렇게 구조화하는 습관을 들여야겠다.