[BOJ] 5427 - 불

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/5427

5427번: 불

난이도: 골드 4

사용언어: JAVA

 

풀이

기본적으로는 BFS를 이용해 문제를 해결할 수 있습니다. 단지 불과 상근이의 위치를 모두 탐색해 주어야 하므로, 큐와 BFS 함수를 따로따로 만들어주었습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/63

[BOJ] 2178 - 미로 탐색

 

불은 빈칸이거나 상근이가 있는 칸으로는 옮겨갈 수 있습니다. (상근이는 불이 오자마자 피할 수 있기 때문에) 그리고 상근이는 빈칸으로만 옮겨갈 수 있습니다. 이렇게 BFS를 반복 수행하여 상근이가 탈출을 할 수 있는지만 확인해주면 됩니다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static class position {
        int x;
        int y;
    }
 
    static int w, h;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 불과 상근이가 움직일 수 있는 좌표 (상,하,좌,우)
    static int cnt = 0;
    static int flag = 0;
    static Queue<position> q_human = new LinkedList<>(); // 상근이의 움직임을 저장할 큐
    static Queue<position> q_fire = new LinkedList<>(); // 불의 움직임을 저장할 큐
 
    public static void bfs_fire(int x, int y, char arr[][]) { // 불의 움직임을 위한 bfs 함수
        int i;
        for (i = 0; i < 4; i++) {
            if (arr[x + d[i][0]][y + d[i][1]] == '.' || arr[x + d[i][0]][y + d[i][1]] == '@') { // 빈 칸이거나 상근이가 있는 칸이면
                position p = new position();
                p.x = x + d[i][0];
                p.y = y + d[i][1];
                arr[x + d[i][0]][y + d[i][1]] = '*'; // 해당 좌표를 불로 표시해주고
                q_fire.add(p); // 큐에 삽입
            }
        }
    }
 
    public static void bfs_human(int x, int y, char arr[][]) { // 상근이의 움직임을 위한 bfs 함수
        int i;
        for (i = 0; i < 4; i++) {
            if (arr[x + d[i][0]][y + d[i][1]] == '.') { // 빈칸이면
                position p = new position();
                p.x = x + d[i][0];
                p.y = y + d[i][1];
                arr[x + d[i][0]][y + d[i][1]] = '@'; // 해당 좌표를 상근이로 표시해주고
                q_human.add(p); // 큐에 삽입
            }
            if (arr[x + d[i][0]][y + d[i][1]] == 0) { // 만약 탈출을 했다면
                System.out.println(cnt + 1); // 횟수 출력
                flag = 1; // 반복문 종료를 위한 flag
                break;
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
        int l;
        for (l = 0; l < T; l++) { // 테스트 케이스 갯수만큼
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s);
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            char[][] arr = new char[h + 2][w + 2];
            int i, j, k;
            for (i = 1; i <= h; i++) { // 테이블 입력
                s = br.readLine();
                for (j = 1; j <= w; j++) {
                    arr[i][j] = s.charAt(j - 1);
                }
            }
 
            for (i = 1; i <= h; i++) {
                for (j = 1; j <= w; j++) {
                    if (arr[i][j] == '@') { // 상근이의 위치를 큐에 삽입
                        position p_human = new position();
                        p_human.x = i;
                        p_human.y = j;
                        q_human.add(p_human);
                    } else if (arr[i][j] == '*') { // 불의 위치를 큐에 삽입
                        position p_fire = new position();
                        p_fire.x = i;
                        p_fire.y = j;
                        q_fire.add(p_fire);
                    }
                }
            }
 
            while (true) {
                k = q_fire.size();
                position p_fire = new position();
                for (i = 0; i < k; i++) { // 불의 위치 이동을 위한 bfs 수행
                    p_fire = q_fire.remove();
                    bfs_fire(p_fire.x, p_fire.y, arr);
                }
                k = q_human.size();
                if (k == 0) { // 상근이가 더 이상 움직일 수 있는 곳이 없다면
                    System.out.println("IMPOSSIBLE"); // 탈출 불가능
                    break;
                }
                position p_human = new position();
                for (i = 0; i < k; i++) { // 상근이의 위치 이동을 위한 bfs 수행
                    p_human = q_human.remove();
                    bfs_human(p_human.x, p_human.y, arr);
                    if (flag == 1) // 이미 탈출 했다면 반복문 탈출
                        break;
                }
                if (flag == 1) // 이미 탈출 했다면 반복문 탈출
                    break;
                cnt++;
            }
           q_fire.clear(); // 큐 및 변수들 초기화
            q_human.clear();
            flag = 0;
            cnt = 0;
        }
    }
}