[백준 Gold 4] 4179 불! - Java

문제링크 : https://www.acmicpc.net/problem/4179

4179번: 불!

 

접근 과정 : 

• https://rays-space.tistory.com/69 

[백준 Gold 4] 5427 불 - Java

• 위 문제와 거의 같은 문제이다.
• 불을 퍼뜨리면서, 지훈이의 위치로 BFS 탐색 해주면 된다.
• 다만, 지훈이가 움직이는 위치에 방문체크를 해서 Queue에 중복저장되지 않게 해야 한다.
• 안그러면 메모리초과가 발생할 것이다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    불! 
*/

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

public class BOJ4179 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        char[][] map = new char[R][C];

        Queue<int[]> jihun = new LinkedList<>();
        Queue<int[]> fire = new LinkedList<>();
        boolean[][] visit = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'J') {
                    jihun.add(new int[] { i, j });
                    map[i][j] = '.';
                    visit[i][j] = true;
                } else if (map[i][j] == 'F') {
                    fire.add(new int[] { i, j });
                }
            }
        }

        int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };


        int count = 0;
        loop: while (true) {

            count++;

            int size = fire.size();

            while (size-- > 0) {
                int[] f = fire.poll();

                for (int i = 0; i < 4; i++) {
                    int nr = f[0] + move[i][0];
                    int nc = f[1] + move[i][1];

                    if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] != '.') {
                        continue;
                    }

                    map[nr][nc] = 'F';
                    fire.add(new int[] { nr, nc });
                }
            }

            size = jihun.size();
            while (size-- > 0) {
                int[] j = jihun.poll();

                for (int i = 0; i < 4; i++) {
                    int nr = j[0] + move[i][0];
                    int nc = j[1] + move[i][1];

                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
                        System.out.println(count);
                        break loop;
                    }

                    if (visit[nr][nc] || map[nr][nc] != '.') {
                        continue;
                    }

                    visit[nr][nc] = true;
                    jihun.add(new int[] { nr, nc });

                }
            }

            if (jihun.isEmpty()) {
                System.out.println("IMPOSSIBLE");
                break;
            }

        }

    }
}

 

P.S 

DFS, BFS등의 탐색을 할 경우에는 역시나 방문체크를 해서 필요없는 경우의 수 또는 연산을 줄이는 게 중요한 것 같다.