문제

지훈씨.. 미로에서 일하느라 고생이 많아요
지훈이가 불에 타기 전에 미로에 탈출할 수 있는지, 얼마나 빨리 탈출할 수 있는지를 출력하면 되는 문제이다.
지훈이와 불은 상하좌우로 이동할 수 있고, 불은 4방향으로 확산된다. 지훈이가 탈출하려면 가장자리에서 탈출해야한다.

풀이 방식

사용한 자료구조

• char[][] maze : 미로를 저장한다.
• boolean[][] visited : 지훈이의 방문 여부 체크를 위한 배열
• int[] dx, dy : 좌표를 네 방향으로 이동시키기 위한 배열
• Queue<Point> q : 불과 지훈이를 이동시키기는 순서를 위한 큐
• Point 객체 : 현재 좌표 x, y와 type(지훈, 불), count 값으로 이동한 시간을 저장한다.

사용한 함수

• bfs(Queue<point> q) : 불과 지훈이를 종료조건일때까지 이동시킨다.
• isEdge(int x, int y) : 입력받은 좌표가 미로의 가장자리인지 판별
  네 방향으로 이동시켰을 때 미로의 범위를 넘어가면 가장자리 인 것
• isRange(int x, int y) : 입력받은 좌표가 미로의 범위 내에 있는지 판별

전체 로직

1. 입력을 받으면서 지훈이의 좌표는 따로 저장해두고, 불인 경우는 queue에 넣어준다.

큐에 불 - 지훈의 순서로 넣는 이유?

불에 탈 수 있는 공간에 지훈이를 위치시키면 안되기 때문에 불을 먼저 확산 -> 지훈 이동

이때지훈이의 위치가 가장자리인 경우는 바로 탈출할 수 있기 때문에 1을 출력하고 종료한다.

2. bfs()를 수행한다.
   • 네 방향으로 이동하면서 범위를 벗어나거나, 벽이거나, 불인 경우는 이동할 수 없으니 continue
   • 다음 방문할 좌표가 !visited[nx][ny] (이전에 방문 X)이고 지훈이면 q에 넣어준다.
   • 불인 경우는 maze에 바로 불이 확산됨을 표시해서 방문 체크를 할 수 있도록 한다.

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

public class BOJ_4179 {
    static int r;
    static int c;
    static char[][] maze;
    static boolean[][] visited;
    static Point jihun;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        r = Integer.parseInt(input[0]);
        c = Integer.parseInt(input[1]);

        maze = new char[r][c];
        visited = new boolean[r][c];
        Queue<Point> q = new LinkedList<>();

        for (int i = 0; i < r; i++) {
            input = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                maze[i][j] = input[j].charAt(0);

                if (maze[i][j] == 'J') {
                    // 시작점에서 바로 탈출 가능한 경우
                    if (isEdge(i, j)) {
                        System.out.println(1);
                        return;
                    }

                    maze[i][j] = '.';
                    jihun = new Point(i, j, 0, 0);
                } else if (maze[i][j] == 'F') {
                    q.add(new Point(i, j, 1, 0));
                }
            }
        }

        bfs(q);
    }

    static void bfs(Queue<Point> q) {
        int x;
        int y;
        int count;

        q.add(jihun); // 불 - 지훈의 순서로 queue에 넣어줌
        visited[jihun.x][jihun.y] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();
            x = p.x;
            y = p.y;
            count = p.count;

            // 종료 조건
            if (isEdge(x, y) && p.type == 0) {
                System.out.println(count + 1);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (!isRange(nx, ny) || maze[nx][ny] == '#' || maze[nx][ny] == 'F') {
                    continue;
                }

                if (p.type == 0 && !visited[nx][ny]) {
                    // 지훈
                    q.add(new Point(nx, ny, p.type, count + 1));
                    visited[nx][ny] = true;
                } else if (p.type == 1) {
                    // 불
                    maze[nx][ny] = 'F';
                    q.add(new Point(nx, ny, p.type, count + 1));
                }
            }
        }

        System.out.println("IMPOSSIBLE");
    }

    /*
     * MAZE의 범위를 벗어나는지 판별
     * @return : 입력받은 좌쵸가 범위 내에 있으면 true
     * */
    static boolean isRange(int x, int y) {
        if (x >= 0 && y >= 0 && x < r && y < c) {
            return true;
        }
        return false;
    }

    /*
     * MAZE의 가장자리인지 판별
     * @return: 가장자리이면 true
     * */
    static boolean isEdge(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (!isRange(nx, ny)) {
                return true;
            }
        }

        return false;
    }

    static class Point {
        int x;
        int y;
        int type;
        int count;

        public Point(int x, int y, int type, int count) {
            this.x = x;
            this.y = y;
            this.type = type;
            this.count = count;
        }
    }
}