[boj] 백준 2636 치즈 (Java) - BFS

[문제]

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

2636번: 치즈

 

[풀이]

1. 가장자리의 치즈만 녹아 없어지고 내부에 공간이 있는 경우 영향을 주지 않는다. 따라서 치즈가 없다고 명시된 (0,0)부터 탐색을 진행하면 가장자리의 치즈만 녹일 수 있다.

2. 치즈가 없으면 큐에 넣고 계속 탐색을 진행하고, 치즈가 있으면 치즈를 녹인 후 탐색을 멈춘다. 한번 BFS가 호출될때마다 가장자리의 치즈가 모두 녹을 것이므로 t를 증가시킨다. 

3. 탐색이 끝나고 남은 치즈의 개수를 확인한다. 모든 치즈가 녹았으면 답을 출력하고, 아직 남아있으면 BFS를 한번 더 돌린다.

 

[코드]

 

package bfs_dfs;

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

public class boj_2636_java {
    static int n, m;
    static int[][] cheese;
    static boolean[][] visited;
    static int[] dr = {0, 0, -1, 1};
    static int[] dc = {-1, 1, 0, 0};
    static int t, count;
    public static void main(String[] args) throws Exception{
        // 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 
        //모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        cheese = new int[n][m];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                cheese[i][j] = Integer.parseInt(st.nextToken());
                if(cheese[i][j]==1) count++; //치즈 조각 개수
            }
        }
        
        bfs();
    }

    public static void bfs(){
        //(0,0)부터 치즈 녹이기
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        visited = new boolean[n][m];
        visited[0][0] = true;

        int melted = 0; //녹은 가장자리 치즈
        t++;
        
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int i=0; i<4; i++){
                int nr = p.r + dr[i];
                int nc = p.c + dc[i];

                if(nr<0 || nc<0 || nr>=n || nc>=m || visited[nr][nc]) continue;

                visited[nr][nc] = true;

                if(cheese[nr][nc]==0){
                    q.add(new Point(nr, nc)); //계속 탐색 진행
                }
                else{
                    //치즈가 녹음
                    cheese[nr][nc] = 0;
                    melted++;
                }
            }
        }

        count -= melted;

        //치즈가 다 녹았다면
        if(count==0){
            System.out.println(t);
            System.out.println(melted);
            return;
        }
        else{
            bfs();
        }
    }

    public static class Point{
        int r, c;
        Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}