# 치즈(2636)

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

감도 안왔다... 여기까지가 한계인건가....

그래도 구글링해서 풀어보다보니까 그—-래도 감은 온다 내일 시험이니까 일단은 흐름파악했다는걸로 만족하자

```java
import java.util.*;
import java.io.*;
public class Main{
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int time = 0;
    static int result = 0;

    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());
        arr = new int[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1)
                    result++;
            }
        }

        while(true){
            visited = new boolean[n][m];
            outair(0, 0);

            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(arr[i][j] == 1 && isEdge(i, j)){
                        dfs(i, j);
                    }
                }
            }

            change();

            changeAir();
            time++;

            int tmp = countCheese();
            if(tmp!=0){
                result = countCheese();
            }else
                break;
        }
        System.out.println(time);
        System.out.println(result);
        //외부공기는 외부공기로 체크를 해둬야함
        //가장자리 치즈를 확인
    }

    //외부공기를 2로 체크
    public static void outair(int x, int y){
        visited[x][y] = true;
        arr[x][y] = 2;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || ny<0 || nx>=n || ny>=m)
                continue;
            if(arr[nx][ny]==0 && !visited[nx][ny])
                outair(nx, ny);
        }
    }

    public static void dfs(int x, int y){
        visited[x][y] = true;
        arr[x][y] = -2;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || ny<0 || nx>=n || ny>=m)
                continue;
            if(arr[nx][ny]==1 && !visited[nx][ny] && isEdge(nx, ny)){
                dfs(nx, ny);
            }
        }
    }

    public static boolean isEdge(int x, int y){
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(arr[nx][ny] == 2)
                return true;
        }
        return false;
    }

    public static void change(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j] == -2)
                    arr[i][j] = 2;
            }
        }
    }

    public static void changeAir(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j] == 2)
                    arr[i][j] = 0;
            }
        }
    }

    public static int countCheese(){
        int cnt=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j]==1)
                    cnt++;
            }
        }
        return cnt;
    }
}
```

BFS버전으로 풀어보기!

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

class Main {
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int cheeseCnt;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    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());
        arr = new int[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1)
                    cheeseCnt++;
            }
        }

        int cnt = 0;
        int time = 0;
        while(cheeseCnt !=0){
            cnt = cheeseCnt;
            time++;
            visited = new boolean[n][m];
            outAir();
        }

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

    public static void outAir(){
        visited[0][0] = true;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        while(!q.isEmpty()){
            int[] xy = q.poll();
            for(int i=0; i<4; i++){
                int nx = xy[0] + dx[i];
                int ny = xy[1] + dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=m || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                if(arr[nx][ny] == 0){
                    q.add(new int[]{nx, ny});
                }else{
                    cheeseCnt--;
                    arr[nx][ny] = 0;
                }
            }
        }
    }

    public static boolean isEdge(int x, int y){
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(arr[nx][ny] == 2 )
                return false;
        }
        return true;
    }

    public static int countCheese(){
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j] == 1)
                    cnt++;
            }
        }
        return cnt;
    }
}


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kyudo97.gitbook.io/library/baekjoon/implementation/2636.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.