백준/그래프 이론

3055 탈출

have a good time 2024. 6. 18. 11:20

 

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


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


public class Main {		
	
		static String map[][];		
		static Queue<Position> water;
		static Queue<Position> animal;
		static int R;
		static int C;
	
	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());	
		water = new LinkedList<>();
		animal = new LinkedList<>();
		map = new String[R][C];		
		
		for(int i= 0; i<R; i++) {
			
			String[] input = br.readLine().split("");
	
			for(int j =0; j<C; j++) {		
				
				String value = input[j];			
				map[i][j] = value;		 
			
				
				// 고슴도치 처음 위치 
				if(value.equals("S")) {
					animal.add(new Position(i,j));
				}
				
				
				// 물 처음 위치 
				if(value.equals("*")) {
					water.add(new Position(i,j));
				}						
				
			}
		}
		
			
		String value = solve();		
		System.out.println(value);	
		
	}
	
	
	
	public static String solve() {
		
		String result = "";
		int time = 0;
		
		int dx [] = {-1,1,0,0};
		int dy [] = {0,0,-1,1};	
		
		solve2 :
		while(true) {		
					
			// 고슴도치가 더 이상 갈 곳이 없다는 뜻이므로 while 문 나옴. 
			if(animal.isEmpty()) {
				result = "KAKTUS";
				break solve2;
			}				
			
			time++;		
			
			// 1. 물 이동
			int water_size = water.size();
			
			// 매 시간마다 각 위치에 있는 물이 이동해야 하므로 water_size(각 위치 물의 수) 만큼 for 문 돌림. 
			for(int i=0; i<water_size; i++) {
				
				Position p = water.poll();
				
				int water_x = p.x;
				int water_y = p.y;			
			
				for(int j=0; j<4; j++) {
					
					int nextX = water_x + dx[j];
					int nextY = water_y + dy[j];					
					
					if(nextX>=0 && nextX<R && nextY>=0 && nextY<C) {
				    
							// 물이 이동할 수 있는 곳
							// 1. S 가 아니고 -> 물은 비어있는 곳으로만 이동 가능하므로 고슴도치가 있는 곳 안됨. 
							// 2. D 비버의 굴이 아니고
							// 3. X 돌이 아닌
							
							// A는, 과거에 고슴도치가 이동한 곳. -> 지금은 비어있는 공간이므로 물이 이동 가능함.  
							if(map[nextX][nextY].equals(".") || map[nextX][nextY].equals("A")) {
								
								// 물로 됨. 
								map[nextX][nextY] = "*";
								water.add(new Position(nextX, nextY));
								
							}					
					}		
					
				}	
			
			}
		
			
			// 2. 고슴도치 이동			
			int animal_size = animal.size();		
			
			for(int i= 0; i<animal_size; i++) {
				
				Position p = animal.poll();
				int animal_x = p.x;
				int animal_y = p.y;
				
				for(int j=0; j<4; j++) {
					
					int nextX = animal_x + dx[j];
					int nextY = animal_y + dy[j];					
					
					if(nextX>=0 && nextX<R && nextY>=0 && nextY<C) {	  										
							
							// 고슴도치가 도착지에 도착했으므로 while 문 나옴
							if(map[nextX][nextY].equals("D")) {
								result = Integer.toString(time);
								break solve2;
							}
							
							// 고슴도치가 이동할 수 있는 곳	
							// S가 아니고, 물(*)이 아니고, 돌(X)이 아닌 곳	
							// A(고슴도치가 과거에 있던 곳)도 아닌 장소 => 메모리 문제
							if(map[nextX][nextY].equals(".")) {
								
								// 다음번에 고슴도치가 S나 A 인 곳에 이동하지 않도록 표시함
								// 그래야 메모리 초과 안 남.
								
								// S : 고슴도치가 이번에 이동할 곳
								map[nextX][nextY] = "S";	
								
								// A : 고슴도치가 이동 직전에 원래 있던 곳
								map[animal_x][animal_y] = "A";
								
								animal.add(new Position(nextX, nextY));
								
							}					
					}		
					
				}			
				
			}	
		
			result = Integer.toString(time);
		
		}
		
		return result;	
		
	}
	
}

 

 

 

 

 

 

 

 

1. 핵심

일단 이 문제에서 핵심은 

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 

=>  하나의 while 문 내에서 매 분, 물과 고슴도치가 이동하는 것을 처리하는데

물 이동을 먼저 하면 된다. 

 

 

 

2. 핵심

코드대로 진행하면,

예제 입력 2에서

다음과 같은 상황이 된다. 

 

 

 

[1]

D  .    *

.    .    .

.    .   S

 

 

 

[2]

D  *   *

.    .   *

.    S  A

 

-> 일단 코드에서 보이듯이

고슴도치가 이동했을 때, S 표시(녹색)를 해준다.

이 전에 있던 위치는 헷갈리지 않도록 A (노랑색)표시함.

 => 다음번에 고슴도치는 S나 A 인 곳으로 이동하지 않게 해야 메모리 초과 안 나옴 

 

 

[3]

 

D   *   *

.    *    *

S   A   * 

 

-> 물은 첫번째 고슴도치가 있던 곳(노랑색)에도 이동 가능함.

 

 

[4]