[백준(JAVA)] 3055번: 탈출

문제

✔ 난이도 - Gold 4

설명

bfs
물 먼저 for문 돌면서 인접한 곳 다 물로 채우고 *
그다음에 고슴도치 이동하는데 원래 있던곳으로 다시 돌아가면 안되니까 나온곳은 X 표시

1분마다 위의 두가지를 반복해야한다.
따라서 각각 queue를 두고
각각의 queue의 현재 크기만큼이 1분동안 실행되어야할 작업이므로 queue.size() 만큼 물 확장과 고슴도치 이동을 진행한다.

물이 더 이상 퍼질 곳이 없더라도 고슴도치는 계속 움직여야 함
메인 루프는 고슴도치가 움직일 수 있을 때까지(!sQueue.isEmpty()) 돌기

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        Queue<int[]> sQueue = new LinkedList<>();
        Queue<int[]> wQueue = new LinkedList<>();

        char[][] graph = new char[R][C];
        for(int i = 0; i < R; i++){
            char[] cArr = br.readLine().toCharArray();
            for (int j = 0; j < C; j++){
                char c = cArr[j];
                graph[i][j] = c;
                if (c == '*') wQueue.offer(new int[] {i, j});
                if (c == 'S') sQueue.offer(new int[] {i, j, 0});
            }
        }
        // System.out.println(Arrays.deepToString(graph));
        // 입력받기 완료

        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};

        while(!sQueue.isEmpty()){
            //물 확장 먼저
            int waterSize = wQueue.size();
            for (int i = 0; i < waterSize; i++){
                int[] waterNode = wQueue.poll();
                int wCR = waterNode[0];
                int wCC = waterNode[1];

                for (int j = 0; j < 4; j++){
                    int wNR = wCR + dr[j];
                    int wNC = wCC + dc[j];

                    if (wNR < 0 || wNC < 0 || wNR >= R || wNC >= C || graph[wNR][wNC] != '.') continue;

                    wQueue.offer(new int[] {wNR, wNC});
                    graph[wNR][wNC] = '*';
                }
            }

            // 고슴도치 이동
            int sSize = sQueue.size();
            for (int i = 0; i < sSize; i++){
                int[] sNode = sQueue.poll();
                int sCR = sNode[0];
                int sCC = sNode[1];
                int sMinute = sNode[2];

                for (int j = 0; j < 4; j++){
                    int sNR = sCR + dr[j];
                    int sNC = sCC + dc[j];

                    if (sNR < 0 || sNC < 0 || sNR >= R || sNC >= C) continue;
                    if (graph[sNR][sNC] == 'D') {
                        sb.append(sMinute + 1);
                        System.out.println(sb);
                        return;
                    } 
                    // * X S 제외
                    if (graph[sNR][sNC] == '.') {
                        sQueue.offer(new int[] {sNR, sNC, sMinute+1});
                        graph[sNR][sNC] = 'X';
                    }
                }
            }
        }
        System.out.println("KAKTUS");
    }
}

⏰ 시간복잡도

$O(N^2)$