[백준 3055] 탈출 (java, bfs)

[백준 3055] 탈출 (java, bfs)

문제 출처 : 링크

숲의 2차원 배열 : int [R][C]

비어있는 곳 : '.'

물이 차있는 지역 : '*'

돌 : 'X'

도착지점 : 'D'

고슴도치 위치 : 'S'

물이 차있는 지역은 시간이 지날 때마다 상하좌우로 퍼지게 되고, 동시에 고슴도치는 한 칸을 움직인다.

물에 막히기 전에 도착지점까지 도착할 수 있는지 확인하는 문제다.

숲의 2차원 배열을 입력할 때, 고슴도치와 물이 차있는 지역에 대한 행과 열을 큐에 각각 저장하고, bfs를 통해 이동 시간을 구했다.

큐를 2개로 진행하는 bfs는 처음해봐서 조금 어려웠지만, 원리는 크게 다르지 않았다.

둘다 큐에 들어온 size만큼 반복문을 돌려 진행하고, 고슴도치의 큐 사이즈가 0이 되어버리면 이동이 불가능한 것이며 고슴도치가 D에 도착한다면 현재 진행된 카운트 수를 출력하면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
class map1 {
    int y;
    int x;
    
    map1(int y, int x){
        this.y = y;
        this.x = x;
    }
}
 
public class Main3055 {
 
    static int R,C;
    static char[][] map;
    static Queue<map1> q1;
    static Queue<map1> q2;
    
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int cnt;
    static int min;
    static String fail = "impossible";
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        
        R = Integer.parseInt(str[0]);
        C = Integer.parseInt(str[1]);
        
        q1 = new LinkedList<>(); // 고슴도치
        q2 = new LinkedList<>(); // 물
        
        map = new char[R][C];
        
        for (int i = 0; i < R; i++) {
            str = br.readLine().split("");
            for (int j = 0; j < C; j++) {
                map[i][j] = str[j].charAt(0);
                if(str[j].charAt(0) == 'S') q1.add(new map1(i,j));
                if(str[j].charAt(0) == '*') q2.add(new map1(i,j));
            }
        }
        
        cnt = 0;
        
        bfs(map);
        
        System.out.println(cnt);
        
    }
    
    public static void bfs(char[][] map) {
        
        while(true){
            
            cnt++;
            
            int size2 = q2.size();
            
            for (int s = 0; s < size2; s++) {
                map1 m1 = q2.poll();
                
                for (int i = 0; i < 4; i++) {
                    int ny = m1.y + dy[i];
                    int nx = m1.x + dx[i];
                    
                    if(ny >= 0 && nx >= 0 && ny < R && nx < C){
                        if(map[ny][nx] == '.'){
                            map[ny][nx] = '*';
                            q2.add(new map1(ny,nx));
                        }
                    }
                }
            }
            
            if(q1.size() == 0){
                System.out.println(fail);
                System.exit(0);
            }
            
            int size1 = q1.size();
            
            for (int s = 0; s < size1; s++) {
                map1 m1 = q1.poll();
                
                for (int i = 0; i < 4; i++) {
                    int ny = m1.y + dy[i];
                    int nx = m1.x + dx[i];
                    
                    if(ny >= 0 && nx >= 0 && ny < R && nx < C){
                        if(map[ny][nx] == 'D'){
                            return;
                        }
                        
                        if(map[ny][nx] == '.'){
                            map[ny][nx] = 'S';
                            q1.add(new map1(ny,nx));
                        }
                    }
                }
            }
            
        }            
    }
 
}