[BOJ - JAVA] 4179 - 불! (BFS)

# 주소

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

4179번: 불!

# 문제 

# 문제 해설 및 코드 리뷰

import java.util.*;
class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Main{
    static int n, m;
    static int[][] arr;
    static boolean[][] visit;
    static boolean[][] visit2;
    static int dir[][] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
    static Queue<Point> queue = new LinkedList<>();
    static Queue<Point> fire = new LinkedList<>();
    static int time = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        visit2 = new boolean[n][m];
        for(int i = 0; i < n; i++){
            String str = scan.next();
            for(int j = 0; j < m; j++){
                if(str.charAt(j) == '#'){
                    arr[i][j] = 1;
                }else if(str.charAt(j) == 'J') {
                    queue.offer(new Point(i, j));
                    arr[i][j] = 0;
                    visit[i][j] = true;
                }else if(str.charAt(j) == 'F') {
                    fire.offer(new Point(i,j));
                    arr[i][j] = -1;
                    visit2[i][j] = true;
                }
                else
                    arr[i][j] = 0;
            }
        }
        while(true){
            time++;
            if(queue.size() == 0) {
                System.out.println("IMPOSSIBLE");
                break;
            }
            boom();
            bfs();
        }
    }
    static void bfs(){
        int size = queue.size();
        for(int k = 0; k < size; k++){
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                    System.out.println(time);
                    System.exit(0);
                }
                if(arr[nx][ny] == 1)
                    continue;
                if(arr[nx][ny] == -1)
                    continue;
                if(visit[nx][ny])
                    continue;
                queue.offer(new Point(nx,ny));
                visit[nx][ny] = true;
            }
        }
    }
    static void boom(){
        int size = fire.size();
        for(int k = 0; k < size; k++){
            Point now = fire.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(arr[nx][ny] == 1)
                    continue;
                if(visit2[nx][ny])
                    continue;
                if(arr[nx][ny] == 0){
                    fire.offer(new Point(nx,ny));
                    arr[nx][ny] = -1;
                    visit2[nx][ny] = true;
                }
            }
        }
    }
}

이제 그래프 탐색 문제는 어느정도 숙련이 된 것 같습니다.

골드4, 5 문제 수준은 원큐에 정답이 될 때도 있네요.

이번 문제의 경우는 그렇지 못했습니다. 계속 정답률 76%근처에서 틀렸다고 나오더라고요.

같이 살펴보겠습니다.

이 문제는 J는 주인공의 위치, F는 불이 발화한 위치를 뜻하고 #은 벽, .은 공간을 의미합니다.

저는 문자로 탐색하는 것을 굉장히 싫어하기 때문에 입력문으로 문자를 받고 숫자로 치환해서 푸는걸 선호합니다.

따라서 2차원 배열의 arr를 선언하여 진행하겠습니다.

 

static int n, m;
static int[][] arr;
static boolean[][] visit;
static boolean[][] visit2;
static int dir[][] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
static Queue<Point> queue = new LinkedList<>();
static Queue<Point> fire = new LinkedList<>();
static int time = 0;

n x m크기의 배열이므로 n과 m을 static으로 선언합니다.

그리고 arr와 주인공의 방문 여부를 탐색할 visit과 불의 방문 여부를 탐색할 visit2를 static에 선언합니다.

또한 4가지 방향에 대해서만 움직임을 제시해야하므로 dir를 방향기저로 설정하고 마찬가지로 주인공의 움직임을 담을 queue와 불의 움직임을 담을 fire을 Queue자료구조를 이용하여 풀어보겠습니다.

for(int i = 0; i < n; i++){
    String str = scan.next();
    for(int j = 0; j < m; j++){
        if(str.charAt(j) == '#'){
            arr[i][j] = 1;
        }else if(str.charAt(j) == 'J') {
            queue.offer(new Point(i, j));
            arr[i][j] = 0;
            visit[i][j] = true;
        }else if(str.charAt(j) == 'F') {
            fire.offer(new Point(i,j));
            arr[i][j] = -1;
            visit2[i][j] = true;
        }
        else
            arr[i][j] = 0;
    }
}

제일 먼저, #이 들어오면 arr에 1을 입력받습니다.

그리고 J가 들어오면 주인공의 위치이므로 arr는 0을 넣고 queue에 인덱스를 삽입합니다.

또한 F가 들어오면 불의 위치이므로 arr에는 -1을 넣고 fire에 인덱스를 삽입하겠습니다.

외의 경우에는 빈 공간이므로 0을 삽입하면 되겠습니다.

이후 bfs문과 boom 함수 두 가지를 살펴봅시다.

static void bfs(){
    int size = queue.size();
    for(int k = 0; k < size; k++){
        Point now = queue.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                System.out.println(time);
                System.exit(0);
            }
            if(arr[nx][ny] == 1)
                continue;
            if(arr[nx][ny] == -1)
                continue;
            if(visit[nx][ny])
                continue;
            queue.offer(new Point(nx,ny));
            visit[nx][ny] = true;
        }
    }
}

bfs함수는 다음과 같습니다.

이번에도 역시 queue의 크기를 size에 담고 size만큼 탐색을 진행해야 합니다.

왜냐하면 시간이 경과하면서 bfs문을 탐색하는 문제같은 경우엔, 1번 탐색하고 time을 증가시키고 다시 bfs문을 실행시키도록 로직을 짜야하기 때문인데요.

지금처럼 boom문을 실행하고 bfs를 실행하도록 하여 어떤 결과가 나오는지 살펴봅시다.

size만큼 탐색을 진행할 때 인덱스의 가장자리에 도달하면 탐색을 종료하고 time을 출력하도록 짤 것입니다.

그리고 arr가 1이거나 -1일 때(벽과 불) 모두 continue;시켜버리고 나머지 경우에 대해서 queue와 visit을 담고 true로 바꿉니다.

visit이 사용되어야 하는 이유는 간단합니다.

주인공의 위치를 방문 처리해주지 않으면 무한 루프에 빠져서 쓸데없이 시간낭비할 수 있기 때문입니다.

bfs문에서 visit문은 필수와 다름없습니다.

자 그럼 bfs는 이렇게 탐색할 수 있고 boom함수도 살펴볼까요?

static void boom(){
    int size = fire.size();
    for(int k = 0; k < size; k++){
        Point now = fire.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if(arr[nx][ny] == 1)
                continue;
            if(visit2[nx][ny])
                continue;
            if(arr[nx][ny] == 0){
                fire.offer(new Point(nx,ny));
                arr[nx][ny] = -1;
                visit2[nx][ny] = true;
            }
        }
    }
}

boom함수 역시 마찬가지로 fire의 크기를 size에 담아서 size만큼 탐색을 진행합니다.

이 때에는 지정된 범위 밖으로 불이 번지거나 하지 않기 때문에 범위 외의 경우엔 continue시켜주고 arr가 1일 때, 그리고 방문한 지점도 continue시켜줍니다.

또한 arr가 0일 때에만 fire에 nx,ny를 담아주고 arr값을 -1로 모두 변경한 뒤 visit2 = true로 삽입합니다.

그럼 시간이 1time씩 증가할 때 마다 상,하,좌,우로 불이 뻗어나가게 됩니다.

이 모든 작업이 bfs()와 boom()이 한 세트로 일어날 때마다 time은 1씩 증가합니다.

따라서

while(true){
    time++;
    if(queue.size() == 0) {
        System.out.println("IMPOSSIBLE");
        break;
    }
    boom();
    bfs();
}

만약 queue가 0이 된다면 더 이상 queue에 담을 빈 공간이 없다는 뜻이므로 IMPOSSIBLE을 출력하게 로직을 짭니다.

그리고 그렇지 않을 경우엔 boom()함수와 bfs()함수를 실행하여 주시면 되겠습니다.

만약 가장자리에 도달했을 때엔 bfs()함수의 이동 안에서 이루어져야 한다는 것을 유념하시기 바랍니다.

감사합니다.