[Baekjoon 5427 / Java / 골드4] 불

문제

테스트 케이스

 

 

BFS 문제이다. 불이 1초마다 상하좌우로 1칸씩 퍼지고, 상근이는 1초마다 상하좌우로 1칸씩 이동할 수 있다.

건물 끝 4방향의 '.' 빈 공간에 다다르면 탈출에 성공하게 된다.

 

상근이의 빌딩 탈출에 걸리는 시간을 출력하고, 탈출할 수 없다면 IMPOSSIBLE을 출력하면 된다.

 

import java.io.*;

import java.util.*;

public class 불_5427 {

    static int N; // 테스트 케이스 개수

    static int[] dx = {-1, 1, 0, 0};

    static int[] dy = {0, 0, -1, 1};

    static char[][] tower;

    static int[][] visited;

    static int w, h;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        // 테스트 케이스 개수만큼 반복

        for(int i = 0; i < N; i++) {

            // 입력받기

            StringTokenizer st = new StringTokenizer(br.readLine());

            w = Integer.parseInt(st.nextToken());

            h = Integer.parseInt(st.nextToken());

            tower = new char[h][w];

            visited = new int[h][w];

            for(int j = 0; j < h; j++) {

                String line = br.readLine();

                for(int k = 0; k < w; k++) {

                    tower[j][k] = line.charAt(k);

                    visited[j][k] = -1;

                }

            }

            // BFS 진행하고 결과 출력

            System.out.println(fire());

        }

    }

    // 진행할지 말지 알려주는 함수

    public static boolean goingNoGoing(int nx, int ny, char who) {

        // 불일 경우

        if(who == '*') {

            // tower 안에 있고 빈 공간 또는 상근이 시작 위치일때 True

            if(0 <= nx && nx < h && 0 <= ny && ny < w && (tower[nx][ny] == '.' || tower[nx][ny] == '@')) {

                return true;

            }

            return false;

        }

        // 상근이일 경우

        else {

            // tower 안에 있고 아직 안 간 빈 공간일때 true

            if(0 <= nx && nx < h && 0 <= ny && ny < w && visited[nx][ny] == -1 && tower[nx][ny] == '.') {

                return true;

            }

            return false;

        }

    }

    // bfs 메인 로직

    public static String fire() {

        // 큐 사용

        Queue<int[]> queue = new LinkedList<>();

        int start[] = new int[2];

        // 불이 먼저 진행되어야 하므로 먼저 큐에 넣는다

        for(int i = 0; i < h; i++) {

            for(int j = 0; j < w; j++) {

                // 불일 경우 큐에 삽입

                if(tower[i][j] == '*') {

                    queue.add(new int[]{i, j, '*'});

                }

                // 상근이 시작 위치 저장만 해두기 ( 지도에 @는 하나뿐이다 )

                if(tower[i][j] == '@') {

                    start[0] = i;

                    start[1] = j;

                }

            }

        }

        // 상근이 시작 위치 큐에 삽입 + visited 처리

        queue.add(new int[]{start[0], start[1], '.'});

        visited[start[0]][start[1]] = 0;

        // bfs 시작

        while(!queue.isEmpty()) {

            // 큐에서 좌표 꺼내기

            int[] here = queue.poll();

            int x = here[0];

            int y = here[1];

            char who = (char)here[2];

            // 탈출 조건 ( 상근이가 4방향 중 어느 한쪽 끝에 도달했다면 )

            if(who == '.' && (x == 0 || x == h-1 || y == 0 || y == w-1)) {

                // 거리를 String 형태로 return한다

                return String.valueOf(visited[x][y] + 1);

            }

            // 4방향 진행

            for(int i = 0; i < 4; i++) {

                int nx = x + dx[i];

                int ny = y + dy[i];

                // 진행할 수 있을 때

                if(goingNoGoing(nx, ny, who)) {

                    // 불이라면 진행시키고 큐에 넣기

                    if(who == '*') {

                        tower[nx][ny] = '*';

                        queue.add(new int[]{nx, ny, '*'});

                    }

                    // 상근이라면 visited 거리 갱신하고 큐에 넣기

                    else {

                        visited[nx][ny] = visited[x][y] + 1;

                        queue.add(new int[]{nx, ny, '.'});

                    }

                }

            }

        }

        return "IMPOSSIBLE";

       

    }

}

 

큐를 이용해서 BFS를 하되, while문에 들어가기 전 불의 시작 좌표를 먼저 입력한다. 그러면 이후 while문이 진행될 때 자연스럽게 불 상근이 불 상근이 불 상근이 순서로 불이 먼저 진출하게 된다. 불과 상근이가 겹치면 안 되기 때문에 불을 먼저 진행시키고 상근이가 피해 가는 것이다.

 

또한 건물 지도와 동일한 크기의 visited 배열을 만들어서 각 위치마다 걸리는 시간을 저장해 두고, 건물 끝에 도달했다면 해당 위치까지 걸린 시간 + 1한 값을 return 해 준다. 

만약 while문이 끝날 때까지 탈출하지 못했다면 IMPOSSIBLE을 return 한다.