[백준] 불 5427 (Java)

문제 링크

https://www.acmicpc.net/problem/5427

나의 풀이

• 기본적으로 최소시간을 구하는 문제라 BFS를 사용했습니다.
• 그리고 문제를 '불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다' 라는 문장이 있습니다. 즉, 불이 먼저 동서남북으로 한 칸씩 번지게 한 다음에 상근이가 동서남북으로 움직일 수 있는지 구별해야 합니다.

구현 기능

• 불은 동서남북으로 한 칸씩 번져야 한다.
  • 단, 벽에는 불이 붙을 수 없다.
• 상근이도 동서남북으로 한 칸씩 움직일 수 없다.
  • 역시 벽으로는 이동할 수 없고, 불이 붙으려는 칸으로 이동할 수 없다. -> 불을 먼저 번지게 함으로써 구별
• 상근이가 x,y 좌표 중 하나라도 map의 가장자리에 도착하게 되면 탈출가능한 경우이다.

막혔던 점

• sBfs()함수의 while문 바로 다음에 나오는 for문의 조건에 pSize가 아닌 person.size()를 바로 넣게 되면 해당 person.size가 계속 동적으로 변하는 걸 간과하고 코딩을 해서 25%에서 계속 틀렸습니다.
  • person은 상근이의 위치정보를 저장하는 Queue입니다.

Code

package bfs.boj_5427;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static char[][] maps;

    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] dx = new int[]{-1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    static Queue<int[]> fireLocation;
    static Queue<Point> person;

    static int row;
    static int col;

    public static void main(String[] args) throws IOException {

        int testcases = Integer.parseInt(br.readLine());

        for (int i = 0; i < testcases; i++) {
            inputData();
        }
    }

    static void inputData() throws IOException {
        st = new StringTokenizer(br.readLine());

        col = Integer.parseInt(st.nextToken());
        row = Integer.parseInt(st.nextToken());

        maps = new char[row][col];


        fireLocation = new LinkedList<>();
        person = new LinkedList<>();

        for (int i = 0; i < row; i++) {
            maps[i] = br.readLine().toCharArray();
            for (int j = 0; j < col; j++) {
                if (maps[i][j] == '*') {

                    fireLocation.offer(new int[]{i,j});


                }
                if (maps[i][j] == '@') {
                    person.offer(new Point(i, j, 0));
                }
            }
        }

        int res = sBfs();
        if(res > 0){
            System.out.println(res);
        }
        else{
            System.out.println("IMPOSSIBLE");
        }
    }

    static void fireBfs() {
        int fires = fireLocation.size();

        for (int j = 0; j < fires; j++) {
            int[] poll = fireLocation.poll();
            int x = poll[0];
            int y = poll[1];


            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (0 <= nx && nx < row && 0 <= ny && ny < col) {
                    if (maps[nx][ny] == '.' || maps[nx][ny] == '@') {
                        fireLocation.offer(new int[]{nx,ny});
                        maps[nx][ny] = '*';
                    }
                }
            }
        }
    }

    static int sBfs() {
        while (!person.isEmpty()) {
            fireBfs();

//            person.stream().forEach(x -> System.out.print(x.toString()));
            int pSize = person.size();
            for (int k = 0; k < pSize; k++) {
                Point poll = person.poll();
                int x = poll.x;
                int y = poll.y;

                int dis = poll.dis;
                if (x == 0 || x == row - 1 || y == 0 || y == col - 1) {
                    return dis+1;
                }

                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (0 <= nx && nx < row && 0 <= ny && ny < col) {
                        if (maps[nx][ny] == '.') {
                            maps[nx][ny] = '@';
                            person.offer(new Point(nx,ny,dis+1));

                        }
                    }
                }
            }
        }
        return 0;

    }

    static class Point{
        int x;
        int y;
        int dis;

        public Point(int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", dis=" + dis +
                    '}';
        }
    }
}

Git

https://github.com/youngh0/java-algorithm/blob/master/algorithm/src/main/java/bfs/boj_5427/Main.java