[백준] 2636: 치즈 - JAVA

30 May 2023 in Algorithm on 구현

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

풀이

구현 + 그래프탐색문제였다.

공기와 맞닿아있는 치즈는 한 시간이 지나면 녹는다.

치즈 내부에 구멍이 있을 수 있는데 외부 공기와 연결되어있지 않으면 치즈를 녹이지 않는다.

판의 가장자리는 치즈가 놓이지 않으므로 (0,0)은 항상 공기이다.

(0,0)부터 시작하여 BFS탐색을 통해 공기면 Quque에 넣어주고, 치즈면 녹인다.

• 참고

  1. static int[] dr = { 1, -1, 0, 0 }; static int[] dc = { 0, 0, 1, -1 };

  2. static int[][] vector = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

  사방탐색을 할 때 1번 코드보다 2번 코드로 하는 것이 메모리 소모가 적다.

---

메모리: 15832KB

시간: 160ms

언어: Java 11

코드

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

public class Main {

    public static class Node {
        int r;
        int c;

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

    }

    static int[][] vector = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, cnt, time;
    static int[][] board;

    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());
        board = new int[N][M];
        cnt = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1) {
                    cnt++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        time = 0;
        while (cnt > 0) {
            int now = bfs();
            if (now > 0) {
                time++;
            }

            if (cnt - now == 0) {
                sb.append(time).append("\n");
                sb.append(cnt).append("\n");
            }

            cnt -= now;
        }

        System.out.println(sb);

    }

    private static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0));

        boolean[][] visit = new boolean[N][M];
        visit[0][0] = true;

        int remove = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nr = node.r + vector[i][0];
                int nc = node.c + vector[i][1];

                if (nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc]) {
                    continue;
                }

                if (board[nr][nc] == 0) {
                    queue.add(new Node(nr, nc));
                } else {
                    remove++;
                    board[nr][nc] = 0;
                }

                visit[nr][nc] = true;
            }
        }

        return remove;

    }

}