[백준] 4179 불! - Java

 

 

 

문제 출저

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

4179번: 불!

 

 

 

문제 풀이

2차원 배열에 지훈, 벽, 불이 줄어진다. 

지훈이는 1초에 상하좌우 중 한 곳을 움직이고 불은 1초에 4방향으로 퍼진다.

지훈이와 불은 벽으로는 이동하지 못한다.

지훈이는 2차원 배열 가장자리를 넘으면 탈출한다.

이 때 탈출에 필요한 최소 시간을 구해야 한다. (탈출이 불가능할 경우 IMPOSSIBLE 을 출력)

 

 

BFS를 이용해 풀었습니다.

헷갈렸던 점은 불과 지훈 중 누가 먼저 움직이는 거 였습니다.

하지만 잘 생각해보면 불을 먼저 움직이게 로직을 만들어야 한다는 것을 알 수 있습니다.

지훈이가 먼저 움직이더라도 불이 덮치면 말이 안되기 때문입니다.

 

불을 먼저 움직인다음 지훈이를 움직이게 로직을 짰습니다.

또한 지훈이가 가장 자리를 넘어가면 탈출한 것으로 간주하여 탐색을 멈추고 정답을 출력했습니다. 

 

 

 

소스 코드 

package baekjoon.backjoon10.day0110.day10;




import javax.sound.sampled.Line;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


/*
불!
https://www.acmicpc.net/problem/4179

가장 자리에서 탈출 할 수 있다.

지훈이는 4방향 중 한 방향
불은 4방향 확산
벽은 통과 못함

반례 모음
5 5
FFFFF
..J..
.....
.....
.....

4


3 3
.FF
..J
...

1


3 3
..F
.J#
.#.

2

 */
public class B4179 {

    static int r,c;
    static char[][] board;

    static boolean[][] visited;
    static Queue<dot> jihun;
    static Queue<dot> fire;

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



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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        board = new char[r][c];

        jihun = new LinkedList<>();
        fire = new LinkedList<>();

        visited = new boolean[r][c];

        for(int i = 0; i < r; i++) {
            String str = br.readLine();
            for(int j = 0; j < c; j++) {
                board[i][j] = str.charAt(j);

                if(board[i][j] == 'J') {
                    jihun.add(new dot(i,j));
                    board[i][j] = '.';
                    visited[i][j] = true;
                }
                else if(board[i][j] == 'F') {
                    fire.add(new dot(i,j));
                }
            }
        }

        simulation();



    }

    public static void simulation() {

        // 불이 먼저 붙고 지훈이 이동

        int count = 0;
        boolean escape = false;


        while (!jihun.isEmpty()) {

            if (escape) {
                break;
            }

            Queue<dot> nextJihun = new LinkedList<>();
            Queue<dot> nextFire = new LinkedList<>();

            // 4방향으로 불이 번짐
            while (!fire.isEmpty()) {
                dot d = fire.poll();
                for(int i = 0; i < 4; i++) {
                    int ny = d.y + dy[i];
                    int nx = d.x + dx[i];

                    if(boardCheck(ny,nx)) {
                        board[ny][nx] = 'F';
                        nextFire.add(new dot(ny,nx));
                    }
                }
            }

            // 지훈이의 움직임
            while (!jihun.isEmpty()) {
                dot d = jihun.poll();
                for(int i = 0; i < 4; i++) {
                    int ny = d.y + dy[i];
                    int nx = d.x + dx[i];

                    // 경계로 탈출
                    if(ny == -1 || nx == -1 || ny == r || nx == c) {
                        escape = true;
                    }
                    else if(boardCheck(ny,nx) && visited[ny][nx] == false) {
                        visited[ny][nx] = true;
                        nextJihun.add(new dot(ny,nx));
                    }

                }
            }


            count += 1;

            fire = nextFire;
            jihun = nextJihun;

        }

        if(escape == false) {
            System.out.println("IMPOSSIBLE");
        }
        else {
            System.out.println(count);
        }


    }


    public static boolean boardCheck(int y, int x) {
        if(y >= 0 && y < r && x >= 0 && x < c && board[y][x] == '.') {
            return true;
        }
        else {
            return false;
        }
    }



    public static class dot {
        int y;
        int x;

        dot(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

}