[JAVA]5427 불 골드4

 📚 문제  

5427번: 불

🔍 아이디어  

bfs로 해결하였습니다.

 

한 타임에는 불이 퍼지는 경우와 내가 이동하는 경우를 모두 생각해야했습니다. 또한 이번 타임에 불이 옮겨지는곳에는 자신이 이동하면 안된다는 조건이있습니다.

 

저의 경우 불이 옮겨 붙어지는 경우를 모두 계산한 후에 이동하지 않고 이동할 수 있는 모든 경우를 이동한 후에, 불이 이동하도록 하였습니다. 이렇게 한 후 다음턴에 자신의 위치가 불로 변한 경우 해당 칸은 이전에 갈 수 없던 칸이었는데 이동한것으로 하여 무시하는 방식으로 진행하였습니다.

 

상근이가 이미 다녀간 위치는 @로 표기하여 상근이가 다시 방문하지 않도록 하였고, 불이 옮겨붙는 칸은 '.' 과 '@'로 하여 불이 옮겨 붙을 수 있도록 하였습니다. 이후에 만약 상근이가 외각에 도착한 경우 이동한 칸의 개수를 리턴하도록 하고 만약 상근이가 더 이상갈 수 있는 곳이 없다면 -1을 리턴하여 IMPOSSIBLE을 파악하도록 하였습니다.

 

 

 

📝 풀이 

import java.awt.*;
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 Boj_5427_불 {
    private static int w, h;
    private static char[][] map;
    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    private static Queue<Point> me = new LinkedList<>();
    private static Queue<Point> fires = new LinkedList<>();

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

        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            map = new char[h][w];
            me.clear();
            fires.clear();

            for (int i = 0; i < h; i++) {
                map[i] = br.readLine().toCharArray();
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == '*') {
                        fires.add(new Point(i, j));
                    } else if (map[i][j] == '@') {
                        me.add(new Point(i, j));
                    }
                }
            }

            int mvCnt = findExit();
            if (mvCnt == -1) {
                sb.append("IMPOSSIBLE");
            } else sb.append(mvCnt);

            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static int findExit() {

        int mvCnt = 0;
        while (!me.isEmpty()) {
            //내가 갈수있는거 한칸 가기
            mvCnt++;
            int myCnt = me.size();

            for (int i = 0; i < myCnt; i++) {
                Point now = me.poll();
                if (map[now.x][now.y] == '*') continue;//내가 있는곳에 불이있으면 그곳으로는 과거에 가면 안됐기 때문

                if (now.x == 0 || now.y == 0 || now.x == h - 1 || now.y == w - 1) {
                    return mvCnt;
                }

                for (int[] dir : dirs) {
                    int mvX = now.x + dir[0];
                    int mvY = now.y + dir[1];

                    if (0 <= mvX && 0 <= mvY && mvX < h && mvY < w && map[mvX][mvY] == '.') {
                        map[mvX][mvY] = '@'; //상근이가 이미 다녀갔다표시
                        me.add(new Point(mvX, mvY));
                    }
                }
            }


            //불 옮기기
            int fireCnt = fires.size();
            for (int i = 0; i < fireCnt; i++) {
                Point poll = fires.poll();
                for (int[] dir : dirs) {
                    int mvX = poll.x + dir[0];
                    int mvY = poll.y + dir[1];
                    if (0 <= mvX && 0 <= mvY && mvX < h && mvY < w && (map[mvX][mvY] == '.' || map[mvX][mvY] == '@')) {
                        map[mvX][mvY] = '*';
                        fires.add(new Point(mvX, mvY));
                    }
                }
            }
        }
        return -1;
    }


}