백준 2636번 : 치즈 java

이 문제는 너비 우선 탐색을 이용하여 다음에 없어질 치즈들을 큐에 저장한 후에 그다음 시간에 모든 치즈들이 사라지면 순회를 종료하는 알고리즘입니다.

이 문제를 풀 때 조심하셔야 하는 점은 밖의 공기와 접한 치즈들만 녹아서 없어진다는 것입니다.

위의 그림에서 없어지는 부분들을 확인해 보시면 안의 공기와 맞닿은 부분들은 녹지 않는데 밖의 공기와 맞닿은 부분들만 녹습니다.

따라서 우리는 밖의 공기와 접해 있는 치즈의 부분들만 큐에 넣은 후 제거해야 한다느 것을 알 수 있습니다.

또한 이 문제를 풀 때 공기와 맞닿은 치즈 부분들을 바로 큐에서 제거하면 안됩니다.

다음 차례에서 모든 치즈들이 사라진다면 남아 있는 치즈들의 개수를 세야 하는데 치즈들을 바로 없애면 이를 할 수 없기
때문입니다.

따라서 저는 이 문제를 해결할 때 밖의 공기들을 탐색하면서 큐를 하나 더 만들어 제거할 치즈들을 또 다른 큐에 담아서
탐색이 끝난 후 치즈들을 제거해주었습니다.

코드를 확인하시면서 이 부분을 집중해서 보시면 좋을 것 같습니다.

---

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

public class Main {
    static int row, col, cheese, time = 0;
    static int[][] map;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        cheese = row * col;

        map = new int[row][col];

        for(int i = 0; i<row; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j<col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if(map[i][j] == 0)
                    cheese--;
            }
        }

        if(cheese == 0){
            System.out.println(0);
            System.out.println(0);
            return;
        }

        bfs();

        int sum = 0;
        for(int i = 0; i<row; i++)
            for(int j = 0; j<col; j++)
                if(map[i][j] == 1)
                    sum++;

        System.out.println(time);
        System.out.println(sum);
    }

    static void bfs(){


        while(true) {
            Queue<Node> q = new LinkedList<>();
            Queue<Node> remove = new LinkedList<>();
            q.offer(new Node(0, 0));

            //밖의 공기와 맞닿은 치즈들을 확인
            boolean[][] visited = new boolean[row][col];
            visited[0][0] = true;
            while(!q.isEmpty()){
                Node a = q.poll();

                for(int i = 0; i<4; i++){
                    int dr = a.row + dR[i];
                    int dc = a.col + dC[i];

                    if(dr<0||dc<0||dr>=row||dc>=col)
                        continue;
                    if(visited[dr][dc])
                        continue;

                    if(map[dr][dc] == 0){
                        visited[dr][dc] = true;
                        q.offer(new Node(dr, dc));
                    }
                    if(map[dr][dc] == 1) {
                        visited[dr][dc] = true;
                        remove.offer(new Node(dr, dc));
                        cheese--;
                    }
                }
            }

            time++;
            if (cheese == 0)
                break;

            //공기와 맞닿은 치즈들을 제거
            while (!remove.isEmpty()) {
                Node a = remove.poll();
                map[a.row][a.col] = 0;
            }
        }
    }
}
class Node{
    int row, col;

    Node(int row, int col){
        this.row = row;
        this.col = col;
    }
}

cheese 변수에 남아있는 치즈들이 몇 개나 있는지를 저장하여 cheese가 0이 되면 종료하게 만들었습니다.