치즈2636

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

문제를 읽다가 치즈에 구멍이 있다길래 뭔소린지 했는데
표시된 부분이 치즈의 구멍이다..

저 상태는 구멍이 닫힌 상태라서 공기가 없단다. 그래서 구멍안에서는 공기가 치즈와 닿지 않는단다

하지만 위와 같이 표시된부분이 열리면 공기가 들어와서 치즈가 녹게된다

빙산문제와 비슷하면서도 구멍이 닫힌상태인지 확인해야하는 차이점이 있는 문제이다

구멍이 닫힌상태인지 어떻게 찾을 수 있을란감 구멍안에서 x표시된 부분까지 길찾기를 해야하남

아니면 반대로 0,0 좌표(항상 공기상태니까)에서 부터 시작해서 연결된 공기들을 전부 찾아서 표시 해야 할까 그러면 막힌 구멍은 표시가 안될 테니까

만약 위와 같이 치즈에 구멍이 닫힌 상태로 있다면
0,0 부터 공기만 bfs 든 dfs든 탐색해서 색칠해주면 되지 않을까 싶다

위와 같이 되겄지
색칠 하고 난뒤 색칠한 부분과 접하는 치즈를 녹이면 되겄다

그리고 색칠한거 리셋하고 다시 색칠하고..
반복하면 될거 같다.

녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하면 되겄지

board 를 돌면서 -1(진공상태)로 초기화하고 bfs 로 탐색하면서 0(공기)으로 만들었다
그리고 치즈 녹이고
반복하였다

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

class Pos
{
    int r;
    int c;

    public Pos() {}

    public Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

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

        String[] input = br.readLine().split(" ");

        int R = Integer.parseInt(input[0]);
        int C = Integer.parseInt(input[1]);

        int[][] board = new int[R][C];

        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        int preLeft = 0;
        for(int i = 0; i < R; ++i)
        {
            input = br.readLine().split(" ");
            for(int j = 0;j < C; ++j)
            {
                board[i][j] = Integer.parseInt(input[j]);
                if(board[i][j] == 0)
                    board[i][j] = -1;//진공상태로 만들기
                else
                    preLeft++;
            }
        }

        boolean[][] visit = new boolean[R][C];
        int time = 0;
        int left = 0;

        while(true)
        {
            for(int i = 0; i < R; ++i)
                Arrays.fill(visit[i], false);

            for(int i = 0; i < R; ++i)
            {
                for(int j = 0;j < C; ++j)
                {
                    if(board[i][j] == 0)
                        board[i][j] = -1;//진공상태로 만들기
                }
            }
            //공기채우기 색칠하기
            bfs(new Pos(0, 0), R, C, board, visit, dir);

            for(int i = 0; i < R; ++i)
                Arrays.fill(visit[i], false);

            time++;

            //치즈녹이면서 개수파악하기 //주변 칸이 0이고 visit 하지 않았으면 공기와 접한다
            left = cheese(board, R, C, visit, dir);

            if(left == 0)
                break;

            preLeft = left;
        }
        System.out.println(time);
        System.out.println(preLeft);
    }

    private static int cheese(int[][] board, int R, int C, boolean[][] visit, int[][] dir)//남은 치즈 반환
    {
        int ret = 0;
        for(int i = 0; i < R; ++i)
        {
            for(int j = 0;j < C; ++j)
            {
                if(board[i][j] == 1 && visit[i][j] == false)
                {
                    for(int k = 0; k < 4; ++k)
                    {
                        int r = i+dir[k][0];
                        int c = j+dir[k][1];

                        if(r >= 0 && r < R && c >= 0 && c < C && board[r][c]==0 && visit[r][c] == false)
                        {
                            board[i][j] = 0;
                            visit[i][j] = true;
                            break;
                        }
                    }
                    if(board[i][j] == 1)
                        ret++;
                }

            }
        }

        return ret;
    }

    private static void bfs(Pos start, int R, int C, int[][] board, boolean[][] visit, int[][] dir)
    {
        Queue<Pos> que = new LinkedList<>();
        que.add(start);
        visit[start.r][start.c] = true;
        board[start.r][start.c] = 0;

        while(que.isEmpty() == false)
        {
            Pos cur = que.poll();

            for(int i = 0; i < 4; ++i)
            {
                int r = cur.r + dir[i][0];
                int c = cur.c + dir[i][1];

                if(r >= 0 && r < R && c >= 0 && c <C && board[r][c]==-1)
                {
                    que.add(new Pos(r, c));
                    visit[r][c] = true;
                    board[r][c] = 0;
                }
            }
        }
    }
}