백준 2638번 치즈 2

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 Cheese2 {
    static int N,M;
    static int[][] map;
    static boolean flag = false;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {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());
        map = new int[N][M];
        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());
            }
        }
        int count = 0;
        while (true){
            bfs(0,0);
            if(!flag) break;
            count++;

        }

        System.out.println(count);

    }
    public static void bfs(int row, int col){
        flag = false;
        int[][] copy = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy[i][j] = map[i][j];
            }
        }
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] {row,col});
        boolean[][] visited = new boolean[N][M];
        visited[row][col] = true;
        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 + dr[i];
                int ncol = ccol + dc[i];
                if(nrow<0||ncol<0||nrow>=N||ncol>=M)
                    continue;
                if(visited[nrow][ncol])
                    continue;
                visited[nrow][ncol] = true;
                if(copy[nrow][ncol]!=0){
                    flag = true;
                    visited[nrow][ncol] = false;
                    copy[nrow][ncol] += 1;
                    if(copy[nrow][ncol]>=3){
                        map[nrow][ncol] = 0;
                    }
                }
                else{
                    que.add(new int[]{nrow,ncol});
                }
            }
        }
    }
}

풀이방법

이 문제는 치즈의 두 개의 변이 외부와 맞닿아 있으면, 지워지도록 설계해야 한다.

📢 핵심은 bfs 수행시, 치즈를 만나면 que에 넣지 않는것이 핵심이다.
이렇게 설계하면, 외부와 맞닿은 변이 있는 치즈만 없어진다.
즉, 내부의 치즈는 없어지지 않도록 설계할 수 있다.
여기서, 두개 이상의 변이 맞닿아 있을때만 추가로 처리해주면 된다.
두개 이상의변이 맞닿아 있는지 처리할때, 해당 치즈에 2번이상 들리게 되면,
두개 이상의 변이 맞닿아 있는것이다.

1. 탐색횟수를 세기 위한 copy를 새로 생성해준다. map에 다음 탐색시, 영향을 안끼치게 하도록 하기 위함
2. bfs 탐색시 치즈는 중복해서 탐색이 가능하도록 해야 한다. 그래서 치즈를 만나면 visited = true 처리 해준다.
3. 해당 좌표의 copy 값을 +1 시켜줘서, 값이 총 3이상이라면(기존 치즈값이 1이므로) 해당 좌표의 map을 0처리 해준다.
4. 0일때의 값만 큐에 넣어 준다.
5. map에 1이 없을때까지 bfs를 반복해준다. 1이 있는지는 flag를 통해 체크 해준다.
6. 매 반복마다 count를 증가시키고, 반복이 끝나면 count를 출력한다.

후기

같은 유형의 문제를 푼적이 있었는데, 이번에도 0일때만 que에 넣어야 한다는것을 생각해내지 못했다..
또한 맞닿은 변 탐색을 4방향 탐색을 했었는데, 이러면 내부의 변까지 포함해서 오류가 났다.
bfs 중복 탐색이 가능하도록 하여 횟수를 세고, 문제를 해결할 수 있었다.