[BOJ]4179번 : Fire!

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

4179번: 불!

분류 : BFS , DFS, 다익스트라 알고리즘

 

import java.io.*;
import java.math.*;
import java.util.*;

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    public static PrintWriter out;
    static int[] dx = { 0, -1, 0, 1 };
    static int[] dy = { -1, 0, 1, 0 };
    static char[][] maze;
    static int[][] MoveTime, JohnTime;
    static int R, C;
    static int JHour, FHour;
    static boolean check = false;
    static final int inf = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        
            R = sc.nextInt();
            C = sc.nextInt();
            maze = new char[R][C];
            MoveTime = new int[R][C];
            JohnTime = new int[R][C];
            boolean FireCheck = false;
            Queue<JPoint> John = new LinkedList<JPoint>();
            Queue<FPoint> Fire = new LinkedList<FPoint>();
            for (int r = 0; r < R; r++) {
                String str = sc.next();
                maze[r] = str.toCharArray();
            }
            for(int i=0;i<R;i++)
            {
                for(int j=0;j<C;j++)
                {
                    MoveTime[i][j] = inf;
                }
            }
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (maze[i][j] == 'J') {
                        John.add(new JPoint(i, j));
                        JohnTime[i][j] = 0;
                    } else if (maze[i][j] == 'F') {
                        Fire.add(new FPoint(i, j));
                        FireCheck = true;
                        MoveTime[i][j] = 0;
                    }
                }
            }
            
            FBFS(Fire);
            JBFS(John);

            if (check) {
                System.out.println(JHour);
            } else {
                System.out.println("IMPOSSIBLE");
            }
            out.close();

    }

    private static void JBFS(Queue<JPoint> john) {
        JHour = 1;
        boolean[][] visited = new boolean[R][C];
        loop1: while (!john.isEmpty()) {
            int Jsize = john.size();
            for (int sz = 0; sz < Jsize; sz++) {
                JPoint Jp = john.poll();
                int Jx = Jp.x;
                int Jy = Jp.y;
                visited[Jx][Jy] = true;
                for (int ar = 0; ar < 4; ar++) {
                    int cx = Jx + dx[ar];
                    int cy = Jy + dy[ar];
                    if (cx >= 0 && cx < R && cy >= 0 && cy < C) {
                        if (maze[cx][cy] != '#' && maze[cx][cy] != 'F' && !visited[cx][cy]) {
                            if (MoveTime[cx][cy] > JohnTime[Jx][Jy] + 1) {
                                JohnTime[cx][cy] = JHour;
                                visited[cx][cy] = true;
                                john.add(new JPoint(cx, cy));
                            }
                        }
                    } else {
                        check = true;
                        break loop1;
                    }
                }
            }
            JHour++;
        }
    }

    private static void FBFS(Queue<FPoint> fire) {
        FHour = 0;
        boolean[][] visited = new boolean[R][C];
        while (!fire.isEmpty()) {
            int Fsize = fire.size();
            for (int sz = 0; sz < Fsize; sz++) {
                FPoint Fp = fire.poll();
                int Fx = Fp.x;
                int Fy = Fp.y;
                visited[Fx][Fy] = true;
                for (int ar = 0; ar < 4; ar++) {
                    int cx = Fx + dx[ar];
                    int cy = Fy + dy[ar];
                    if (cx >= 0 && cx < R && cy >= 0 && cy < C)
                        if (maze[cx][cy] != '#' && !visited[cx][cy]) {
                            MoveTime[cx][cy] = FHour + 1;
                            visited[cx][cy] = true;
                            fire.add(new FPoint(cx, cy));
                        }
                }
            }
            FHour++;
        }
    }
}

class JPoint {
    int x;
    int y;

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

class FPoint {
    int x;
    int y;

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

이전 도전에는 시간 초과 맞고 포기했다가 1주일 만에 다시 도전해서 풀어내었다.

풀이 방식은 불의 움직임에 대한 bfs를 하여 시간을 저장해놓고

John이 그 보다 빠른 시간 내에 해당 지점에 갈 수 있는지 없는지 판단 그리고 탈출했는지 안 했는지 판단하여 결과를 출력한다.

꼭 풀고 싶었던 문제였기에 뿌듯하다!!!

 

P.S 03/31일 코드 문제점 발견으로 수정