[백준] 5427번 불 (JAVA)

문제

- 상근이는 빈 공간과 벽으로 이루어진 건물에 갇힘

- 건물의 일부에 불이 났고, 상근이는 출구를 향해 뛰는 중

- 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나감

- 벽에는 불이 붙지 않음

- 상근이는 동서남북 인접한 칸으로 이동 가능. 1초 걸림

- 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 / 이제 불이 붙으려는 칸으로 이동할 수 없음

- 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있음

- 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하기

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

- 탈출할 수 없는 경우에는 "IMPOSSIBLE" 출력

 

해결방법

탈출을 위한 escape 함수와 불이 번지는 burn 함수를 따로 구현하여 문제를 해결하였다. 1초마다 불도 번지고 탈출을 위해 상근이가 움직여야했기 때문에 escape 함수 내에서 burn 함수를 호출해주었다. 각 함수(탈출, 불 번짐)에서는 상우하좌로 뻗어나갈 수 있도록 코드를 구성하였다.

 

코드

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

// 좌표 class
class Node {
    int i;
    int j;

    public Node(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

public class Main {
    static int w, h, nowI, nowJ;
    static char[][] map;
    static Queue<Node> fire;
    static boolean[][] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for(int tc = 1; tc<=T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            map = new char[h][w];
            fire = new LinkedList<>();

            for(int i = 0; i<h; i++) {
                String s = br.readLine();
                for(int j = 0; j<w; j++) {
                    map[i][j] = s.charAt(j);
                    // 상근이의 위치
                    if(map[i][j] == '@') {
                        nowI = i;
                        nowJ = j;
                    }
                    // 불의 위치
                    else if(map[i][j] == '*') {
                        fire.add(new Node(i, j));		// 불 리스트에 저장해 줌
                    }
                }
            }
	    // 현재 위치부터 탈출 시작
            escape(nowI, nowJ);
        }
        System.out.println(sb);
    }
	
    public static void escape(int nowI, int nowJ) {
        Queue<Node> queue = new LinkedList<>();
        visited = new boolean[h][w];
        visited[nowI][nowJ] = true;
        queue.add(new Node(-1, -1));		// 불을 퍼뜨리기 위해 큐에 (-1, -1) 넣어줌
        queue.add(new Node(nowI, nowJ));	// 현재 상근이의 위치 큐에 넣어줌
        int time = -1;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
			
            // (-1, -1)일 때, 불 번짐 함수 호출
            if(now.i == -1 && now.j == -1) {
                burn();		// 불 퍼뜨리기
                // 큐가 비어있지 않으면 다시 또 상근이가 움직일 것이고, 그 때마다 불도 함께 퍼져야 하므로
                if(!queue.isEmpty()) {
                    // (-1, -1) 다시 큐에 추가
                    queue.add(now);
                }
                // 1초 증가
                time++;
                continue;
            }
			
            // 상 우 하 좌
            int[] di = {1, 0, -1, 0};
            int[] dj = {0, 1, 0, -1};

            for(int d = 0; d<4; d++) {
                int ni = now.i + di[d];
                int nj = now.j + dj[d];
				
                // 범위를 벗어나면 상근이가 건물 밖으로 탈출한 것이므로 StringBuilder에 걸린 시간 저장 후 함수 탈출
                if(ni >= h || nj >= w || ni < 0 || nj <0) {
                    sb.append(time+1).append("\n");
                    return;
                }
				
                // 상근이가 접근할 수 있는 곳이라면 큐에 저장
                if(map[ni][nj] == '.' && !visited[ni][nj]) {
                    queue.add(new Node(ni, nj));
                    visited[ni][nj] = true;
                }
            }
        }
	// 탈출 실패했다면 "IMPOSSIBLE" StringBuilder에 저장
        sb.append("IMPOSSIBLE\n");
    }
	
    // 불 번짐 함수
    public static void burn() {
        int size = fire.size();		// 현재 번질 수 있는 불의 개수

        for(int i = 0; i<size; i++) {
            Node now = fire.poll();
			
            // 해당 불의 상 우 하 좌로 불 번짐
            int[] di = {1, 0, -1, 0};
            int[] dj = {0, 1, 0, -1};

            for(int d = 0; d<4; d++) {
                int ni = now.i + di[d];
                int nj = now.j + dj[d];
				
                // 불이 번질 수 있는 위치에 있다면 불 번짐
                if(ni >= 0 && nj >= 0 && ni < h && nj <w && (map[ni][nj] == '.' || map[ni][nj] == '@')) {
                    fire.add(new Node(ni, nj));
                    map[ni][nj] = '*';
                }
            }
        }
    }
}