치즈

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

소스 코드

MAIN

 static class Node {
        int x;
        int y;


        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int N, M;
    static int[][] arr;
    static ArrayList<Node> list;
    static boolean[][] check;
    static int cnt;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        list = new ArrayList<>();

        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) {
                    list.add(new Node(i, j));
                    cnt++;
                }
            }

        }

        int time = 0;

        while (cnt != 0) {
            time++;
            check = new boolean[N][M];
            bfs();
            melting();
        }
        System.out.println(time);

    }

BFS

  public static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0));
        check[0][0] = true;
        arr[0][0] = 2;

        while(!queue.isEmpty()) {
            int x = queue.peek().x;
            int y = queue.poll().y;

            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 (check[nx][ny] || arr[nx][ny] == 1) continue;
                // 외내부 공기 판별을 위해 치즈인 경우도 pass
                //내부 1 패스

                arr[nx][ny] = 2; // 외부 공기라는 의미로 2로 바꿔줌
                queue.add(new Node(nx, ny)); // 공기인 경우만 큐에 넣어줌
                check[nx][ny] = true;
            }
        }
    }

MELTING

 static void melting() {

        for (int i = 0; i < list.size(); i++) {
            int x = list.get(i).x;
            int y = list.get(i).y;
            int Mnt = 0;

            for (int j = 0; j < 4; j++) {
                int nx = dx[j] + x;
                int ny = dy[j] + y;
                if (arr[nx][ny] == 2) {
                    Mnt++;
                }
            }
            if (Mnt >= 2) {
                arr[x][y] = 0;
                cnt--;
                list.remove(i);
                i--;
            }

        }
        }

생각할 것

1. 외부공기와 닿은 치즈가 1시간마다 녹을텐데 내부치즈와 어떻게 구분해서 2로 바꿀것인지
2. 바깥으로 넘어가는 상황 말고 어떤 상황이 또 있을지
3. dfs로는 어떻게 만들지

4번만에 더이상 치즈는 남아있지 않음을 볼 수 있다.

참고

https://minhamina.tistory.com/m/156