[BOJ] 백준 5427 : 불 (java)

🧪 5427 불

---

난이도 : 🌟 골드 4
유형 : 그래프 탐색

5427번: 불

 

📝 문제

---

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

 

출력

 

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

🚧  주의할 점

---

1. char형과 String형에 대해서 크게 생각하지 않고 있었는데 이번 문제로 char형이 사용 가능한 경우 String에 비해 더 많은 메모리와 시간을 아낄 수 있다는 사실을 알았다.

 

2. int size = fire.size(); 이 부분이 중요해보이지 않을 수 있지만 이 코드없이 for문을 fire.size()로 돌리면 fire.offer(new int[] { nx, ny, 0 }); 에 의해 fire의 크기가 달라져 답이 달라지게 된다.

 

🧐 핵심 로직

---

◈  “불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.” 라는 문구가 있기 때문에 BFS에서 불을 먼저 옮겨준다.

 

💻 최종 코드 (688 ms -> char[][] 사용)

---

 

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

public class Main {

    static int w, h, answer;
    static char[][] buildingMap;
    static Queue<int[]> person;
    static Queue<int[]> fire;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i=0; i<t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            buildingMap = new char[h][w];
            person = new LinkedList<>();
            fire = new LinkedList<>();

            for (int j=0; j<h; j++) {
                String line = br.readLine();
                for (int k = 0; k < w; k++) {
                    buildingMap[j][k] = line.charAt(k);

                    if (buildingMap[j][k] == '@') {
                        person.add(new int[]{j, k, 0});
                    } 
                    if (buildingMap[j][k] == '*') {
                        fire.add(new int[]{j, k, 0});
                    }
                }
            }

            answer = 0;
            bfs();

            if (answer == 0) sb.append("IMPOSSIBLE\n");
            else sb.append(answer + "\n");
        }

        System.out.println(sb.toString());

        br.close();
    }

    private static void bfs() {

        while (!person.isEmpty()) {
            int size = fire.size();
            for (int i = 0; i < size; i++) {
                int[] tmp = fire.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = tmp[0] + dx[j];
                    int ny = tmp[1] + dy[j];

                    if (range(nx, ny) && (buildingMap[nx][ny] == '.' || buildingMap[nx][ny] == '@')) {
                        buildingMap[nx][ny] = '*';
                        fire.offer(new int[] { nx, ny, 0 });
                    }
                }

            }

            size = person.size();
            for (int k=0; k<size; k++) {
                int[] tmp = person.poll();
                
                for (int j=0; j<4; j++) {
                    int nx = tmp[0] + dx[j];
                    int ny = tmp[1] + dy[j];

                    if (!range(nx, ny)) {
                        answer = tmp[2] + 1;
                        return;
                    }

                    if (buildingMap[nx][ny] == '.') {
                        buildingMap[nx][ny] = '@';
                        person.offer(new int[] {nx, ny, tmp[2] + 1});
                    }
                }
            }
        }
    }

    private static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<h && y<w;
    }
}

 

💻 String[][] 사용 코드 (1644 ms -> String[][] 사용)

---

 

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

public class Main {

    static int w, h, answer;
    static char[][] buildingMap;
    static Queue<int[]> person;
    static Queue<int[]> fire;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i=0; i<t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            buildingMap = new char[h][w];
            person = new LinkedList<>();
            fire = new LinkedList<>();

            for (int j=0; j<h; j++) {
                String line = br.readLine();
                for (int k = 0; k < w; k++) {
                    buildingMap[j][k] = line.charAt(k);

                    if (buildingMap[j][k] == '@') {
                        person.add(new int[]{j, k, 0});
                    } 
                    if (buildingMap[j][k] == '*') {
                        fire.add(new int[]{j, k, 0});
                    }
                }
            }

            answer = 0;
            bfs();

            if (answer == 0) sb.append("IMPOSSIBLE\n");
            else sb.append(answer + "\n");
        }

        System.out.println(sb.toString());

        br.close();
    }

    private static void bfs() {

        while (!person.isEmpty()) {
            int size = fire.size();
            for (int i = 0; i < size; i++) {
                int[] tmp = fire.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = tmp[0] + dx[j];
                    int ny = tmp[1] + dy[j];

                    if (range(nx, ny) && (buildingMap[nx][ny] == '.' || buildingMap[nx][ny] == '@')) {
                        buildingMap[nx][ny] = '*';
                        fire.offer(new int[] { nx, ny, 0 });
                    }
                }

            }

            size = person.size();
            for (int k=0; k<size; k++) {
                int[] tmp = person.poll();
                
                for (int j=0; j<4; j++) {
                    int nx = tmp[0] + dx[j];
                    int ny = tmp[1] + dy[j];

                    if (!range(nx, ny)) {
                        answer = tmp[2] + 1;
                        return;
                    }

                    if (buildingMap[nx][ny] == '.') {
                        buildingMap[nx][ny] = '@';
                        person.offer(new int[] {nx, ny, tmp[2] + 1});
                    }
                }
            }
        }
    }

    private static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<h && y<w;
    }
}