백준 4179번 : 불! [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

불! 골드 3

 

📖 문제

 

 BFS로 풀 수 있는 문제로

문제에서 탈출구는 끝부분 즉, 행이 0이거나 열이 0 인 곳에 가기만 하면 탈출한다. 

...

.J. //여기서는 8곳이 탈출구이다.

...


.##
.J#   //여기서는 0,0, 1,0 이 탈출구이다.
###

 

또한 매 분마다 불이 퍼지고, 지훈이도 이동하는데

불을 먼저 이동시키고 

지훈이를 이동시키면 된다. 

 

불이 퍼졌을 때 불에 대한 방문 체크와 벽 체크

지훈이는 방문체크, 불과 벽 체크를 하면서 이동하면 된다. 

 

분마다 퍼진 불들을 큐에 넣고 

그 시간에 퍼진 불들만 퍼뜨려야한다. 

아니면 시간과 상관없이 전부 퍼진다. 

 

...
.F.  // 0분 초기상태
...


.F.  // 1분 전 1,1에 있는 불 하나가 퍼졌으므로 이 1개에 대한 불을 퍼뜨린다. 
FFF // 1분 경과
.F.


FFF
FFF // 1분전 있는 0,1 1,0 2,1 2,1 에 있는 불만 퍼뜨린다.
FFF

 

---

🔅 문제 풀이

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

public class Main {
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    static boolean[][] visited;
    static boolean[][] fireVisited;
    static char[][] miro;
    static int[] startPos;
    static Queue<int[]> firePos = new LinkedList<>();

    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());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        miro = new char[r][c];
        visited = new boolean[r][c];
        fireVisited = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                miro[i][j] = line.charAt(j);

                if (miro[i][j] == 'J') {
                    startPos = new int[]{i, j};

                }else if (miro[i][j] == 'F') {
                    firePos.add(new int[]{i, j});
                    fireVisited[i][j] = true;

                    // 벽은 방문표시로 갈 수 없게 만듦
                }else if (miro[i][j] == '#') {
                    fireVisited[i][j] = true;
                    visited[i][j] = true;
                }
            }
        }

        int answer = bfs();
        bw.write(answer == - 1 ? "IMPOSSIBLE" : answer + "");
        bw.flush();
        bw.close();
    }


    // 불 먼저 퍼트리고, 4가지 방향으로 이동
    // 불이 지훈 옆이라면 지훈 자리를 F

    private static int bfs() {
        Queue<int[]> jihoonPosQueue = new LinkedList<>();
        visited[startPos[0]][startPos[1]] = true;
        jihoonPosQueue.add(startPos);
        int time = 0;

        while (!jihoonPosQueue.isEmpty()) {
            fireBfs(); // 불 퍼뜨리기

            int size = jihoonPosQueue.size();
            time++;

            // 1분 후 지훈이 이동 가능한 곳 이동
            while (size--> 0) {
                int[] curPos = jihoonPosQueue.poll();

                // 탈출 가능하면 걸린 시간 반환
                if (escapeCheck(curPos)) {
                    return time;
                }

                for (int i = 0; i < 4; i++) {
                    int nextR = curPos[0] + dy[i];
                    int nextC = curPos[1] + dx[i];

                    // 미로 범위를 넘어서는 지 확인, 방문했는지, 불인지 확인
                    if (boundaryCheck(nextR, nextC, miro)
                            || visited[nextR][nextC]
                            || miro[nextR][nextC] == 'F') continue;

                    jihoonPosQueue.add(new int[]{nextR, nextC});
                    visited[nextR][nextC] = true;
                }
            }
        }
        return -1;
    }

    // 불 이동

    private static void fireBfs() {
        int cnt = firePos.size();

        // 현재 불들을 전파
        while (cnt--> 0 && !firePos.isEmpty()) {
            int[] fire = firePos.poll();

            for (int i = 0; i < 4; i++) {
                int newR = fire[0] + dy[i];
                int newC = fire[1] + dx[i];

                if (boundaryCheck(newR, newC, miro)
                        || miro[newR][newC] == '#'
                        || fireVisited[newR][newC]) continue;

                miro[newR][newC] = 'F';
                fireVisited[newR][newC] = true;
                firePos.add(new int[]{newR, newC});
            }
        }
    }

    // 탈출 체크
    private static boolean escapeCheck(int[] curPos) {
        return curPos[0] == 0 || curPos[0] == miro.length - 1
                || curPos[1] == 0 || curPos[1] == miro[0].length - 1;
    }

    // 미로 범위 체크
    private static boolean boundaryCheck(int newR, int newC, char[][] miro) {
        return newR < 0 || newR >= miro.length
                || newC < 0 || newC >= miro[0].length;
    }


}

 

 

 

❗ 오답노트 / 필요한 지식

1.