백준 3055 탈출 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/3055

풀이는 다음과 같다

import java.util.*;
import java.io.*;


public class Main {
    static int R,C;
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static boolean[][] v1; //물
    static boolean[][] v2; //고슴도치
    static int[] D; //굴 초기 위치
    static int[] S; //고슴도치 초기 위치
    static ArrayList<int[]> W; //물 초기 위치
    static char[][] map;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        v1 = new boolean[R][C];
        v2 = new boolean[R][C];
        D = new int[2];
        S = new int[2];
        W = new ArrayList<>();
        map = new char[R][C];


        for(int r = 0 ; r < R ; r++) {
            map[r] = br.readLine().toCharArray();

            for(int c = 0 ; c < C ; c++) {
                if(map[r][c] == 'D') {
                    D[0] = r;
                    D[1] = c;
                }

                if(map[r][c] == 'S') {
                    S[0] = r;
                    S[1] = c;
                }

                if(map[r][c] == '*') {
                    W.add(new int[] {r, c});
                }

            }
        }

        int answer = BFS();
        if(answer == -1) { //-1이라면 탈출 실패
            bw.write("KAKTUS");
        }
        else {
            bw.write(String.valueOf(answer));
        }



        bw.flush();
        bw.close();





    }
    
    static int BFS() {
        Queue<Node> q = new LinkedList<>(); // r, c, 거리, 물 여부
        
        //물 먼저 다 넣어주기 (멀티소스 BFS)
        for(int[] arr : W) {
            q.add(new Node(arr[0], arr[1], 0, true));
            v1[arr[0]][arr[1]] = true; //물 다시 안감
        }
        
        
        //슴도치는 하나랬으니까 for문이 아니라 이렇게 넣어도 된다
        q.add(new Node(S[0], S[1], 0, false));
        v2[S[0]][S[1]] = true; //고슴도치 다시 안감
        
        while(!q.isEmpty()) {
            Node cur = q.poll();
            int curR = cur.r;
            int curC = cur.c;
            int curCnt = cur.cnt;

			//꺼낸친구가 슴도치에다가 비버구멍도달했으면 거리 반환
            if(!cur.w && curR == D[0] && curC == D[1]) return curCnt;

			
            if(cur.w) { //물이라면
                for(int i = 0 ; i < 4 ; i++) {
                    int nr = curR + dr[i];
                    int nc = curC + dc[i];

                    if(isValid(nr, nc) && !v1[nr][nc] && map[nr][nc] != 'D') {
                    //index 맞고 물 방문 안했고 비버 구멍이 아니라면 이동 가능
                        map[nr][nc] = '*';
                        v1[nr][nc] = true;
                        q.add(new Node(nr, nc, curCnt, true));
                    }
                }
            }
            else { //슴도치라면
                for(int i = 0 ; i < 4 ; i++) {
                    int nr = curR + dr[i];
                    int nc = curC + dc[i];

                    if(isValid(nr, nc) && !v2[nr][nc] && map[nr][nc] != '*') {
                    //index 맞고 슴도치 방문 안했고 장애물 아닐때 이동 가능
                        v2[nr][nc] = true;
                        q.add(new Node(nr, nc, curCnt+1, false));
                    }
                }
            }


        }

        return -1; //끝까지 거리 못구했으면 탈출 실패
    }

    static boolean isValid(int r, int c) {
        if(r < 0 || r >= R || c < 0 || c >= C || map[r][c] == 'X') return false;
        return true;
    }



    static class Node {
        int r,c,cnt;
        boolean w; //물인지 슴도치인지 판별 여부
        
        public Node(int r, int c, int cnt, boolean w) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.w = w;
        }
    }
    

}

알아야 할 내용은 다음과 같다.
고슴도치가 물을 피해 이동해 비버구멍으로 탈출하는 로직을 만들어야 한다.
각각 고슴도치와 물을 BFS로 이동시키며,

고슴도치는 물과 장애물을 피해서
물은 장애물을 피해서
둘이 한꺼번에 한턴에 움직인다.
(if(cur.w)로직과 else 로직이 한꺼번에 움직이는것)

그냥 BFS와 그래프상에서 움직이는 로직은 쉽지만,
여기서 알아둬야 할 내용은

여러개의 위치에 있을 수 있는 물은 하나의 ArrayList에 넣어서 한꺼번에 움직인다.
즉, multiSources BFS이다.

여러번의 BFS는 시간초과가 날 수 있다.
그렇기에 한번의 BFS를 시행하며 시작점을 여러개 넣는것이다.

고쳐야 할 부분

물은 비버 구멍을 침범하지 못하므로 물을 이동시킬 때 아래의 로직이 필요하지만 붙여주지 않아 5분간 디버깅을 했다.

아래 로직을 작성하지 않으면, 탈출해야 할 비버 구멍마저 물이 되어
절대 탈출하지 못할 수 있다.

map[nr][nc] != 'D'

코드에 주석을 달아 알기 쉽도록 작성해놓았다!