[JAVA][BOJ] 3055. 탈출

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

이 문제의 포인트는 위의 문장이라고 생각이 들었다. 그렇다면 같은 시간에는 물이 먼저 이동하고 그 뒤에 고슴도치가 이동한다고 다르게 생각할 수도 있다고 생각하였고

물이 먼저 움직인 후에 고슴도치가 움직이면 되겠다고 생각하였다. 

1. 한 사이클당 물이 한번 번진다.

2. 한 사이클당 고슴도치가 한번 움직인다.

2-1. 고슴도치가 못 움직이게 되면( 빠지는 경우 포함 ) 더이상 Queue에 다시 넣을 노드가 사라지게 됨으로 종료

3. 도착하면 그때 몇 사이클 움직이게 되었는지 파악하여 결과값 출력

물의 좌표와 고슴도치의 좌표를 각각 Queue에 넣고 한사이클당 사이즈만큼만 돌려줌으로써 시간당 한번씩 움직이고 퍼지는 것을 구현하였다.

전체 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main3055_v3 {
    static class Node{
        int i, j;
        Node(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
    static int di;
    static int dj;
    static Queue<Node> water;
    static Queue<Node> go;
    static int cnt;
    static String[][] map;
    static Node node;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int R;
    static int C;
    static boolean[][] visit;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        go = new LinkedList<>();
        water = new LinkedList<>();
        String[] s = br.readLine().split(" ");
        R = Integer.parseInt(s[0]);
        C = Integer.parseInt(s[1]);
        map = new String[R][C];
        visit = new boolean[R][C];
        di = 0;
        dj = 0;
        cnt = Integer.MAX_VALUE;
        node = null;
        for(int i=0; i<R; i++) {
            s = br.readLine().split("");
            for(int j=0; j<C; j++) {
                map[i][j] = s[j];
                if(map[i][j].equals("D")) {
                    di = i;
                    dj = j;
                }else if(map[i][j].equals("S")) {
                    go.offer(new Node(i, j));
                    visit[i][j] = true;
                }else if(map[i][j].equals("*")) {
                    water.offer(new Node(i, j));
                }
            }
        }
        escape(0);
        if(cnt == Integer.MAX_VALUE) {
            bw.write("KAKTUS");
        }else {
            bw.write(""+cnt);
        }
        
        br.close();
        bw.close();
    }    
    
    static void escape(int depth) {
        int ni = 0;
        int nj = 0;
        int size = water.size();
        for(int i=0; i<size; i++) {
            node = water.poll();
            for(int j=0; j<4; j++) {
                ni = node.i+dx[j];
                nj = node.j+dy[j];
                if( ni < 0 || nj < 0 || ni > R-1 || nj > C-1 ) continue;
                if( map[ni][nj].equals("X") || map[ni][nj].equals("D") || map[ni][nj].equals("*")) continue;
                map[ni][nj] = "*";
                water.offer(new Node(ni, nj));
            }
        }
        size = go.size();
        if(size == 0) {
            return;
        }
        for(int i=0; i<size; i++) {
            node = go.poll();
            for(int j=0; j<4; j++) {
                ni = node.i + dx[j];
                nj = node.j + dy[j];
                if( ni < 0 || nj < 0 || ni > R-1 || nj > C-1 ) continue;
                if( map[ni][nj].equals("X") || map[ni][nj].equals("*")) continue;
                if( visit[ni][nj]) continue;
                visit[ni][nj] = true;
                if( map[ni][nj].equals("D")) {
                    cnt = depth+1;
                    return;
                    
                }
                map[ni][nj] = "S";
                go.offer(new Node(ni, nj));
            }
        }
        escape(depth+1);
    }
}