[백준] 4179 - 불! (java)

4179번: 불!

---

풀이 방법

 

(BFS) 다음과 같은 순서로 문제를 풀었다

 

1. J가 동서남북으로 이동할 수 있는 경로를 찾아 이동 위치를 찾고 큐에 넣는다

2. J가 전부 한번 이동 후 불이 번진다. (for문으로 이전에 넣은 불만 번지게 하도록 한다)

3. 1에서 넣은 위치가 불이 번진 위치라면 건너뛴다

J가 불을 피해서 미로의 끝에 도달하면 성공으로 처리하여 구현하였다.

 

문제를 풀면서 주의할 점은

 

1. J가 먼저 이동하고 그다음 불이 번진다.

2. J가 이동하고 J자리에 불이 붙어있으면 실패처리 한다

3. 방문 처리를 하여 재방문 하지 않게 구현한다

---

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

public class Main {
    static int N,M;
    static int res=0;
    static char[][] Board;
    static Queue<FNode> fq = new LinkedList<>();
    static Queue<JNode> jq = new LinkedList<>();
    static boolean[][] visited;

    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Board = new char[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            Board[i] = br.readLine().toCharArray();
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (Board[i][j] == 'F') fq.add(new FNode(i,j));
                if (Board[i][j] == 'J') {
                    Board[i][j] = '.';
                    visited[i][j] = true;
                    jq.add(new JNode(i, j,0));
                }
            }
        }
        move();
        br.close();
    }

    static private void move(){
        while(!jq.isEmpty()){
            int size= jq.size();
            for (int i = 0; i < size; i++) {
                JNode temp = jq.remove();
                if (temp.row == 0 || temp.col == 0 || temp.row == (N - 1) || temp.col == (M - 1)) {
                    if (Board[temp.row][temp.col] == 'F') continue;
                    if(res == 0) res = (temp.count+1);
                    else if(res>temp.count)  res = (temp.count + 1);
                    break;
                }
                for (int j = 0; j < 4; j++) {
                    int nr = temp.row + D[j][0];
                    int nc = temp.col + D[j][1];
                    if (nr < 0 || nc < 0 || nr > N || nc > M) continue;
                    if (Board[nr][nc] == '#' || Board[nr][nc] == 'F') continue;
                    if (visited[nr][nc]) continue;
                    visited[nr][nc] = true;
                    jq.add(new JNode(nr, nc, (temp.count + 1)));
                }
            }
            moveFire();
        }


        if(res==0) System.out.println("IMPOSSIBLE");
        else System.out.println(res);
    }

    private static void moveFire() {
        int size = fq.size();
        for (int i = 0; i < size; i++) {
            FNode temp = fq.remove();
            for (int j = 0; j < 4; j++) {
                int nr = temp.row + D[j][0];
                int nc = temp.col + D[j][1];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                if (Board[nr][nc] == '#' || Board[nr][nc] == 'F') continue;

                Board[nr][nc] = 'F';
                fq.add(new FNode(nr,nc));
            }
        }
    }

    static class FNode{
        int row,col;
        FNode(int r, int c){
            this.row = r;
            this.col = c;
        }
    }

    static class JNode{
        int row,col,count;
        JNode(int r, int c, int cnt){
            this.row = r;
            this.col = c;
            this.count = cnt;
        }
    }
}