[Baekjoon Online Judge] 4179. 불 (Java)

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

핵심

1. BFS를 이용해서 `불`이 각 위치에 도달할 수 있는 최소 시간을 구하기 
2. BFS를 이용해서 `지훈이`가 불을 피해서 테두리로 갈 수 있는지 확인

 

Code (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int INF = Integer.MAX_VALUE;

    private static Pair[] dirs = {
            new Pair(1, 0),
            new Pair(0, 1),
            new Pair(0, -1),
            new Pair(-1, 0),
    };

    private static int[][] board, move;
    private static int R, C;

    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()); // 1 ~ 1,000
        C = Integer.parseInt(st.nextToken()); // 1 ~ 1,000
        board = new int[R][C];
        move = new int[R][C];

        Pair me = new Pair(0, 0);
        List<Pair> fires = new ArrayList<>();
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                char ch = line.charAt(j);
                if (ch == '#') {
                    board[i][j] = -1;
                } else if (ch == 'J') {
                    board[i][j] = INF;
                    me = new Pair(i, j);
                } else if (ch == 'F') {
                    board[i][j] = 0;
                    fires.add(new Pair(i, j));
                } else {
                    board[i][j] = INF;
                }
            }
        }

        for (Pair fire : fires) {
            burn(fire);
        }

        int ans = escape(me);

//        print(board);
//        print(move);

        if (ans == -1) {
            System.out.println("IMPOSSIBLE");
            return;
        }
        System.out.println(ans);

    }

    private static void print(int[][] board) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(board[i][j]);
                System.out.print(' ');
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void burn(Pair start) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[R][C];

        queue.add(start);
        visited[start.getRow()][start.getCol()] = true;

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int curRow = current.getRow();
            int curCol = current.getCol();
            int cnt = board[curRow][curCol] + 1;

            for (Pair dir : dirs) {
                int nextRow = curRow + dir.getRow();
                int nextCol = curCol + dir.getCol();
                Pair next = new Pair(nextRow, nextCol);
                if (nextRow >= 0 && nextRow < R && nextCol >= 0 && nextCol < C && !visited[nextRow][nextCol] && board[nextRow][nextCol] > cnt && board[nextRow][nextCol] != -1) {
                    board[nextRow][nextCol] = cnt;
                    queue.add(next);
                    visited[nextRow][nextCol] = true;
                }
            }
        }
    }

    /**
     * 
     * @param start
     * @return 몇 번만에 탈출할 수 있는지
     */
    public static int escape(Pair start) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[R][C];

        queue.add(start);
        visited[start.getRow()][start.getCol()] = true;

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int curRow = current.getRow();
            int curCol = current.getCol();
            int cnt = move[curRow][curCol] + 1;

            if (curRow == 0 || curRow == R - 1 || curCol == 0 || curCol == C - 1) {
                return cnt;
            }

            for (Pair dir : dirs) {
                int nextRow = curRow + dir.getRow();
                int nextCol = curCol + dir.getCol();
                Pair next = new Pair(nextRow, nextCol);

                if (nextRow >= 0 && nextRow < R && nextCol >= 0 && nextCol < C && !visited[nextRow][nextCol] && board[nextRow][nextCol] > cnt && board[nextRow][nextCol] != -1) {
                    move[nextRow][nextCol] = cnt;
                    queue.add(next);
                    visited[nextRow][nextCol] = true;
                }
            }
        }
        return -1;
    }

    // 좌표
    public static class Pair {
        int row, col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public int getRow() {
            return row;
        }

        public void setRow(int row) {
            this.row = row;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int col) {
            this.col = col;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return getRow() == pair.getRow() && getCol() == pair.getCol();
        }

        @Override
        public int hashCode() {
            return Objects.hash(getRow(), getCol());
        }
    }
}