[BOJ] 백준 3055번 탈출 (Java)

#3055 탈출

난이도 : 골드 5

유형 : 그래프 / BFS 

3055번: 탈출

▸ 문제

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

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

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

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

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

▸ 입력

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

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

▸ 출력

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

 

문제 풀이 🖋  

고슴도치가 비버의 굴로 갈 수 있는 가장 빠른 시간을 출력하는 그래프 문제이므로, BFS탐색을 사용해야겠다.

 

문제 조건

Map  : R x C  (최대 50x50)

구하는 값 : S -> D 가장 빠른시간

 

a) '*' 물은 1초에 상하좌우로 퍼짐 (단, D와 X는 이동 x)

b) 'S'는 상하좌우 중 1칸만 이동 (단, D와 X와 *로 이동 x)

c) 그리고 추가로, 비버는 다음에 물이 찰 공간으로도 이동할 수가 없다.

 

이 문제의 중요한 점은 한 싸이클을 이해하는 것이다.

 

한 싸이클 내부는 다음과 같다.

1) 물이 이동 -> 비버의 이동 (c조건 충족)

2) 한 싸이클에 (비버의 Queue 크기), (물의 Queue크기) 만큼만 돌린다. 

 

첫 번째는 예제 2번으로 예를 들면 쉽다.

원래 비버와 물이 동시에 이동하는 것이지만 물의 이동을 더 빠르게 한 후 비버를 이동시키면 자연스레 조건을 충족시켜줌을 알 수 있다. 그래서 1) 물의 이동과 2) 비버의 이동을 나누어서 로직을 짜야한다.

 

❍ Cycle 1 

물    ->  비버 

D * *      D * *

. . *        . . *

. . S      . S S

 

❍ Cycle 2 

물    ->  비버

D * *      D * *

.  * *       . * *

. S S      S S S

 

❍ Cycle 3 

물    ->  비버

D * *      D * *

* * *      * * *

S S S     S S S -> 이동 x 종료 

 

 

 

그리고 중요한 두 번째는 BFS탐색을 할 때 Queue의 크기를 받아 그 크기만큼 돌려야한다는 것이다.

 

왜냐하면 비버의 이동과 물의 이동에 순서가 있기 때문이다. 

Cycle 1: 물 이동 1 -> 비버 이동 1

Cycle 2: 물 이동 2 -> 비버 이동 2

int size = wq.size();
for(int t=0; t<size; t++) {
        ...
        
}

 

해당 조건을 걸어두지 않고 while문으로 queue가 채워지는 대로 반복을 돌리게되면 순서가 지켜지지 않아 올바른 답이 나오지 않을 것이다.

Cycle 1: 물 이동 1 -> 비버 이동 1-1 -> 물 이동 2 -> 비버 이동 1-2 ...

Cycle 2: 물 이동 4 -> 비버 이동 2-1 -> ...

 

 

 

 

풀이 코드 ✔︎ 

// #3055 graph 탈출 (BFS) 
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int r,c, res = -1;
	static int[][] map;
	static boolean[][] check, wcheck;
	static int[] dx = { -1, 1 ,0 ,0 };
	static int[] dy = { 0 ,0 , -1, 1};
	static Queue<Node> q = new LinkedList<>();
	static Queue<Node> wq = new LinkedList<>();
	
	
	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());
		
		map = new int[r][c];
		check = new boolean[r][c];
		wcheck = new boolean[r][c];
		
		for(int i=0; i<r; i++) {
			String[] line = br.readLine().split("");
		
			// D: 26, S: 41, *: 0, .: 4, X: 46  
			for(int j=0; j<c; j++) {
				map[i][j] = line[j].charAt(0)-42;
				
				if(!line[j].equals(".")) {
					if(line[j].equals("S")) {
						q.add(new Node(i,j,0));
					}else if(line[j].equals("*")) {
						wq.add(new Node(i,j,0));
					}
				}
			}
		}
	
		
		solve();
		System.out.println(res == -1? "KAKTUS" : res);
	}
	
	static void solve() {

		while(true) {
			waterMove();
			
			int size = q.size();
			if(size ==0) break;
			for(int t=0; t<size; t++) {
				Node nxt = q.poll();
				int nmove = nxt.move;
				
				// 고슴도치 이동
				for(int i=0; i<4; i++) {
					int nx = nxt.x +dx[i];
					int ny = nxt.y +dy[i];
					
					if(nx<0 || ny<0 || nx>r-1 || ny>c-1) continue; 
					if(check[nx][ny]) continue;
					
					// 도착 
					if(map[nx][ny] == 26) {
//						System.out.println("goal! "+ (nmove+1));
						res = nmove+1;
						return;
					}
					
					if(map[nx][ny] == 4 && !wcheck[nx][ny]) {
						check[nx][ny] = true;
//						System.out.println("gosum :" +nmove+ "::"+nx+","+ny);
						q.add(new Node(nx,ny,nmove+1));
					}
					
				}
			}
		}
		
		
	}
	
	// 물 이동 
	static void waterMove() {
		int size = wq.size();
		for(int t=0; t<size; t++) {
			Node nxt = wq.poll();
	
			for(int i=0; i<4; i++) {
				int nx = nxt.x +dx[i];
				int ny = nxt.y +dy[i];
				
				if(nx<0 || ny<0 || nx>r-1 || ny>c-1) continue; 
				if(wcheck[nx][ny]) continue;
				
				if(map[nx][ny] == 4) {
					wcheck[nx][ny] = true;
	//				System.out.println("water :" +nmove+ "::"+nx+","+ny);
					wq.add(new Node(nx,ny,0));
				}
				
			}
		}
		
	}
	
	static class Node{
		int x;
		int y;
		int move;
		
		public Node(int x, int y, int move) {
			this.x =x;
			this.y =y;
			this.move =move;
		}
	}
}

 

 

그리고 풀이를 하고나니 Node클래스에 있는 move를 없애고 solve()함수 내에서 count변수를 생성하여 사용하는 것이 더 효율적일 것 같다. 물의 이동에서는 사용하지 않기 때문에 메모리 낭비 같다.