[BOJ] 3055 탈출

접근방법

푸는 과정에서 메모리 초과를 만났는데, 큐의 사이즈만큼 돌리지 않았기 때문이다.
이 문제의 핵심은 큐의 사이즈를 먼저 받아놓고 사이즈만큼 돌려야한다는 것이다.
그래야 1초만큼의 큐만 돌 수 있다. (시간별로 체크해줘야 하기 때문)
큐의 단계만큼 돌리고 싶다면 먼저 사이즈를 받아서 돌려주기!

또한 먼저 물 큐를 돌린 다음 고슴도치 큐를 돌려야 한다. (물이 찰 곳으로도 이동하지 못하기 때문)

다른 사람들 코드를 보니 고슴도치 큐에는 시간을 저장하고, 고슴도치 큐가 빌 때까지 큐를 돌렸다. 고슴도치가 갈 곳이 없으면 끝나기 때문이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int r, c, x, y;
    static char[][] map;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Queue<Water> q = new LinkedList<>();
    static Queue<int[]> bq = new LinkedList<>();
    static int[][] visited;

    static class Water {
        int x, y;
        Water(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    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());

        map = new char[r][c];
        visited = new int[r][c];
        for(int i = 0; i < r; i++) {
            map[i] = br.readLine().toCharArray();
        }

        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(map[i][j] == 'D') {
                    x = i;
                    y = j;
                }
                if(map[i][j] == '*') {
                    q.add(new Water(i, j));
                }
            }
        }

        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(map[i][j] == 'S') {
                    bq.add(new int[] {i, j});
                }
            }
        }

        check();
        if(visited[x][y] == 0){
            System.out.println("KAKTUS");
        } else {
            System.out.println(visited[x][y]);
        }
    }

    static void check() {
        int sec = 0;
        while(visited[x][y] == 0 || !bq.isEmpty()) {
            bfs(sec);
            bfs2(sec);
            sec++;
        }
    }
    static void bfs(int sec) {
        int size = q.size();
        for(int j = 0; j < size; j++) {
            Water curT = q.poll();
            int x = curT.x;
            int y = curT.y;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if (map[nx][ny] == '*' || map[nx][ny] == 'X' || map[nx][ny] == 'D') continue;
                if(visited[nx][ny] != 0) continue;
                map[nx][ny] = '*';
                visited[nx][ny] = sec+1;
                q.add(new Water(nx, ny));
            }
        }
    }

    static void bfs2(int sec) {
        int size = bq.size();
        for(int j = 0; j < size; j++){
            int[] xy = bq.poll();
            int x = xy[0];
            int y = xy[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if (map[nx][ny] == '*' || map[nx][ny] == 'X') continue;
                if(visited[nx][ny] != 0) continue;
                visited[nx][ny] = sec+1;
                if(map[nx][ny] == 'D') return;
                bq.add(new int[]{nx, ny});
            }
        }
    }
}