[백준] 3055번 : 탈출

3055번: 탈출

[2개의 Queue를 이용한 BFS]

이와 비슷한 문제지만 좀더 어려운 문제가 '백조의 호수'라고 생각된다. 이 문제를 풀었다면 아래 문제도 풀어보길 추천하는 바다.

[백준] 3197번 : 백조의 호수

고슴도치의 위치를 넣을 큐 Q와 물의 위치를 넣을 큐 waterQ를 준비한다.

 

입력을 받을 때 '*'이라면 waterQ에 넣고, 'S'라면 Q에 넣고 그 때의 위치 (i, j)를 방문한다. 'S'는 단 하나만 존재한다. 문제에서 '고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.' 라고 했으므로 물에 관한 BFS를 먼저 실행시켜 물이 찬 다음 고슴도치를 움직여야 할 것이다.

 

* waterBFS()

int size에 waterQ의 사이즈를 저장해두고, size만큼 반복문을 돌리며 상하좌우 물의 영역을 넓혀나간다. 이 때 넓힌 영역의 위치를 waterQ에 넣는다.

 

* animalBFS()

임시의 큐 tmpQ를 준비한다. Q를 다 비울 때 까지 반복문을 돌며 고슴도치가 갈 수 있는 곳을 방문하고, 그 때의 위치를 tmpQ에 넣는다.

마지막에 Q = tmpQ 해서 복사한다.

 

# Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
    }

    static int r, c, time = 0;
    static boolean flag;

    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static char[][] map = new char[51][51];
    static boolean[][] visit = new boolean[51][51];
    static Queue<Point> waterQ = new LinkedList<>(), Q = new LinkedList<>();

    static void waterBFS(){

        int size = waterQ.size();

        for(int i=0; i<size; i++){
            Point p = waterQ.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > r || nx > c || map[ny][nx] == 'D' || map[ny][nx] == 'X' || map[ny][nx] == '*') continue;

                map[ny][nx] = '*';
                waterQ.add(new Point(ny, nx));
            }
        }
    }
    static void animalBFS(){

        Queue<Point> tmpQ = new LinkedList<>();

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++) {
                int ny = y + Y[a];
                int nx = x + X[a];

                if (ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx] || map[ny][nx] == 'X' || map[ny][nx] == '*') continue;

                if(map[ny][nx] == 'D') flag = true;

                visit[ny][nx] = true;
                tmpQ.add(new Point(ny, nx));
            }
        }
        Q = tmpQ;
    }

    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());

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++){
                map[i][j] = str[j-1];
                
                if(map[i][j] == 'S') {
                    visit[i][j] = true;
                    Q.add(new Point(i, j));
                }
                
                else if(map[i][j] == '*')
                    waterQ.add(new Point(i, j));
            }
        }

        while(true){
            time++;
            waterBFS();
            animalBFS();

            if(flag) break;
            if(Q.size() == 0){
                System.out.println("KAKTUS");
                System.exit(0);
            }
        }
        System.out.println(time);
    }
}