[JAVA]백준 4179번: 불!

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

4179번: 불!

1. 문제 설명

 

지훈이가 미로에 있다.

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기 전에 탈출할 수 있는지, 있다면 얼마나 빨리 탈출할 수 있는지를 결정해야 한다.

 

아래와 같은 규칙이 있다.

• 지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로 이동한다.
• 지훈이는 미로의 가장 자리와 접한 공간에서 탈출할 수 있다.
• 지훈이와 불은 벽이 붙은 공간을 통과하지 못한다.
• 불은 각 지점에서 네 방향으로 확산된다.

지훈이가 미로를 탈출할 수 없는 경우 IMPOSSIBLE를 출력하고, 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

2. 풀이

 

BFS로 풀 수 있다.

 

주의해야 할 점은 불과 지훈이가 동시에 이동한다는 점이다.

 

따라서 지훈이와 불이 동일한 시간 X초에 동일한 위치에 도착하게 된다면 지훈이는 불타게 되는 것이다.

 

나머지는 기본적인 BFS 탐색과 같다.

 

동시에 이동하는 것을 고려하기 위해서는 2가지 구현 방식이 있다.

 

첫 번째는, 불과 지훈이의 위치를 따로 queue에 저장하고 불부터 이동시키는 것이다.

 

동시에 이동한다고 했지만 중요한 것은 불이다.

 

동일한 시간에 불이 도착한 곳에 지훈이가 갈 수 없고, 지훈이가 도착한 곳에 불이 도착하면 지훈이는 불탄다.

 

따라서 임의대로 불부터 이동시켜도 문제가 없다.

 

두 번째는, 불과 지훈이를 같은 queue에 넣고 동시에 이동시키는 것이다.

 

이때, 지훈이는 이동하려는 공간이 빈 공간인 경우에만 이동하며, 불은 이동하려는 공간이 지훈이가 지나간 곳이거나 빈 공간일 때만 이동한다.

 

여기서, 불 또한 빈 공간만 이동하게 된다면 동일한 시간에 동일한 위치에 도착하는 것을 탐지하지 못하게 된다. (하나의 큐에 넣으면 불, 지훈의 순서가 없기에!)

 

지훈이와 불이 이전에 자신이 이동한 곳으로 가지 않는 이유는 방문 확인이다. (BFS의 방문 확인이다.)

 

방문 확인을 수행하지 않으면, 지훈이가 방금 지나온 곳을 또 지나가고, 또 지나가고... 무한 반복이 가능하다.

 

지훈이는 최소 시간 탈출이 목표고, 따라서 지나온 곳을 다시 지나갈 이유가 없다.

 

불 또한 이미 불이 있는 곳은 불이 나고 있다는 뜻이기에 다시 그곳으로 이동할 이유가 없다.

 

 

 

 

3. 코드

// JAVA 11, 시간 660ms, 메모리 67056KB
// 핵심 : 불과 지훈이가 동시에 이동해야 한다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {

    // 미로
    public static char[][] maze;
    public static int row, column;
    // 네 방향으로 이동
    public static int[][] plus = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 이동하는 위치 저장
        Queue<Point> queue = new LinkedList<>();
        boolean escape=false;
        int answer = 0;

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

        row = Integer.parseInt(st.nextToken());
        column = Integer.parseInt(st.nextToken());

        maze = new char[row][column];

        for (int x = 0; x < row; x++) {

            String temp = br.readLine();

            for (int y = 0; y < column; y++) {
                maze[x][y] = temp.charAt(y);

                if(maze[x][y]=='J' || maze[x][y]=='F')
                    queue.add(new Point(x, y));

            }
        }

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int x = 0; x < size; x++) {
                Point now = queue.poll();

                // 지훈이는 탈출 할 수 있을까?
                if (isEscape(now.x, now.y)) {
                    escape = true;
                    break;
                }

                for (int idx = 0; idx < 4; idx++) {
                    int next_x = now.x + plus[idx][0];
                    int next_y = now.y + plus[idx][1];

                    if(next_x<0 || next_x>=row || next_y<0 || next_y>=column)
                        continue;

                    if ((maze[now.x][now.y] == 'F' && maze[next_x][next_y] == 'J')|| maze[next_x][next_y]=='.') {
                        queue.add(new Point(next_x, next_y));
                        maze[next_x][next_y] = maze[now.x][now.y];
                    }
                }
            }
            if(escape)
                break;

            answer++;
        }

        if(escape)
            bw.write(String.valueOf(answer + 1));
        else
            bw.write("IMPOSSIBLE");

        bw.flush();


    }

    // 지훈이가 탈출할 수 있을 것인지 판단
    public static boolean isEscape(int x, int y) {
        if (maze[x][y] == 'J') {
            if(x==0 || x==row-1 || y==0 || y==column-1)
                return true;
        }
        return false;
    }


    // 좌표 저장 클래스
    static class Point{
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}