백준 2636번 치즈

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Cheese {
    static int N;
    static int M;
    static int[][] map;

    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static int cheesecnt = 0;
    static int precheesecnt = 0;
    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());
        map = new int[N][M];
        int count =0;
        for(int i =0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==1)
                    cheesecnt++;
            }
        }
        while(true){
            if(cheesecnt==0)
                break;
            count++;
            precheesecnt = cheesecnt;
            bfs(0,0);
        }

        System.out.println(count);
        System.out.println(precheesecnt);

    }
    
    public static void bfs(int row, int col){
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{row,col});
        while (!que.isEmpty()){
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];
            for(int i =0; i<4; i++){
                int nrow = crow +dx[i];
                int ncol = ccol + dy[i];
                if(nrow<0||ncol<0||nrow>=N||ncol>=M)
                    continue;
                if(visited[nrow][ncol])
                    continue;
                visited[nrow][ncol] = true;
                if(map[nrow][ncol]==1){
                    map[nrow][ncol] = 2;
                    cheesecnt--;
                    continue;
                }
                que.add(new int[] {nrow,ncol});

            }
        }
    }
}

풀이방법

1. 테두리만 없애기 위해 bfs탐색시 현재 칸은 visited변수로 체크해주고, map에서 1인경우를 만나면 해당 칸을 2로 바꿔준다. 이때 1일경우 해당 칸은 큐에 넣지 않는다(내부탐색은 못하도록)
2. map에 치즈가 없을때 까지 bfs를 반복한다.
3. 이때 bfs전 치즈갯수를 precheesecnt에 저장하여 한시간 전 치즈의 갯수를 출력한다.

후기

bfs로 테두리를 없앨 수 있다는 것만 알았다면 쉬운 문제였다.
처음에 동서남북 for문으로 테두리를 없애려 했는데 그렇게 하면 안 없어지는 부분이 있었다...
충분히 bfs떠올릴만 한 문제였는데 아쉽다.