백준 5427번
https://www.acmicpc.net/problem/5427

문제

---

생각하기

---

• BFS 문제이다.

• 메모리가 자꾸 부족하다고 나와서 고생했다.

동작

que가 너무 커지지 않도록 하는게 관건인 것 같다

• isVisited를 사용해서 중복 방문피하기

• 불은 fires배열을 통해서 관리하고 que에서는 하나만 들어가도록 하기

• que에 들어가는 객체에 너무 많은 데이터를 넣으면 안되는것 같다.

결과

코드

---

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static char[][] map = new char[1001][1001];
    private static final int[] dirX = {0, 1, 0, -1}; // 우 하 좌 상
    private static final int[] dirY = {1, 0, -1, 0}; // 우 하 좌 상

    private static Coordinate start;
    private static LinkedList<Coordinate> fires;

    private static class Coordinate {
        int x;
        int y;
        int time;

        private Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Coordinate(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    } // End of Coordinate

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            input();

            bw.write(solve());
        }

        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int ret = BFS();
        if (ret == -1) {
            sb.append("IMPOSSIBLE");
        } else {
            sb.append(ret);
        }
        sb.append('\n');

        return sb.toString();
    } // End of solve()

    private static int BFS() {
        LinkedList<Coordinate> que = new LinkedList<>();
        boolean[][] isVisited = new boolean[N][M];

        que.offer(new Coordinate(-1, -1));
        que.offer(new Coordinate(start.x, start.y));
        isVisited[start.x][start.y] = true;

        while (!que.isEmpty()) {
            Coordinate current = que.poll();

            if (current.x == -1) {
                burn();
                if (!que.isEmpty()) {
                    que.offer(current);
                }
                continue;
            }


            for (int i = 0; i < 4; i++) {
                int nextX = dirX[i] + current.x;
                int nextY = dirY[i] + current.y;

                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
                    // 탈출
                    return current.time + 1;
                }
                if (isVisited[nextX][nextY] || map[nextX][nextY] != '.') continue;
                isVisited[nextX][nextY] = true;
                que.offer(new Coordinate(nextX, nextY, current.time + 1));
            }
        }

        return -1;
    } // End of BFS()

    private static void burn() {
        int size = fires.size();

        for (int i = 0; i < size; i++) {
            Coordinate current = fires.poll();

            for (int j = 0; j < 4; j++) {
                int nextX = dirX[j] + current.x;
                int nextY = dirY[j] + current.y;

                if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && map[nextX][nextY] == '.') {
                    fires.offer(new Coordinate(nextX, nextY));
                    map[nextX][nextY] = '*';
                }
            }
        }
    } // End of burn()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        fires = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = temp.charAt(j);

                if (map[i][j] == '@') {
                    map[i][j] = '.';
                    start = new Coordinate(i, j);
                } else if (map[i][j] == '*') {
                    fires.offer(new Coordinate(i, j));
                }
            }
        }
    } // End of input()
} // End of Main class