[Algo] 백준 4179 불! JAVA

문제 바로가기 : https://www.acmicpc.net/problem/4179

메모리 : 69328KB

시간 : 640ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int r, c;
        int time;

        Node(int r, int c, int time) {
            this.r = r;
            this.c = c;
            this.time = time;
        }
    }

    static int[][] vector = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    static Queue<Node> jihun, fire;
    static int R, C, ans;
    static boolean[][] visitJihun;
    static char[][] map;
    static boolean flag = false;

    public static <T> 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());
        map = new char[R][C];
        jihun = new LinkedList<>();
        fire = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'F') {
                    fire.add(new Node(i, j, 0));
                } else if (map[i][j] == 'J') {
                    jihun.add(new Node(i, j, 0));
                }
            }
        }
        visitJihun = new boolean[R][C];
        ans = 0;
        while (!flag && (!jihun.isEmpty() || !fire.isEmpty())) {
            run();
            ans++;
        }
        if (!flag) {
            System.out.println("IMPOSSIBLE");
        } else {
            System.out.println(ans);
        }

    }

    private static void run() {
        while (!fire.isEmpty()) {
            if (fire.peek().time > ans) {
                break;
            }
            Node f = fire.poll();
            for (int k = 0; k < 4; k++) {
                int x = f.r + vector[k][0];
                int y = f.c + vector[k][1];
                if (x < R && y < C && x >= 0 && y >= 0 && map[x][y] == '.') {
                    fire.add(new Node(x, y, f.time + 1));
                    map[x][y] = 'F';
                }
            }
        }
        while (!jihun.isEmpty()) {
            if (jihun.peek().time > ans) {
                break;
            }
            Node j = jihun.poll();
            for (int k = 0; k < 4; k++) {
                int x = j.r + vector[k][0];
                int y = j.c + vector[k][1];
                // 밖으로 벗어나면 탈출
                if (x >= R || y >= C || x < 0 || y < 0) {
                    flag = true;
                    return;
                }
                // 탈출아니면 다음 칸으로 이동할수있나?
                if (!visitJihun[x][y] && map[x][y] == '.') {
                    visitJihun[x][y] = true;
                    jihun.add(new Node(x, y, j.time + 1));
                }
            }
        }
    }
}

풀이

bfs를 이용한 구현문제. 지훈이와 불 중에 무엇을 먼저 이동시켜야하는지 잘 생각해봐야 할 문제였다. 문제상 불과 지훈은 동시에 이동하기때문에 불을 먼저 이동시켜야 불이 붙은 위치로 이동하지못한다.