[백준 2636] 치즈 (Java)

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

2636번: 치즈

접근 방법

바깥 공기와 접촉해 있는 치즈 부분을 탐색해 제거하기 위해 우선 바깥 공기와 내부 공간을 구별해야했다.

(1, 1)부터 bfs를 통해 0인 공간을 -1로 변경하였다. (내부공간은 탐색되지 않으니 그대로 0)

 

그 다음 이 중 for문으로 치즈 가장자리(해당 좌표에서 상, 하, 좌, 우에 -1이 한 번이라도 있는 경우)를 찾아 bfs탐색한다. 이 때 녹아야할 치즈를 바로 녹이면 다음 탐색에 영향을 주기 때문에 탐색 예정이란 표시로 값을 2로 변경해주고, 녹을 예정인 좌표들을 meltingQueue에 담아준다.

 

가장자리 탐색이 완료되면 날짜++해주고, meltingQueue의 사이즈를 pre에 담아준다. pre는 녹일 예정일 치즈 면적 개수를 담는 변수로, 치즈가 모두 녹기 한 시간 전 남은 치즈 면적은 마지막에 녹여야할 치즈 면적과 동일하다.

 

마지막으로 meltingQueue에 담긴 좌표의 값을 -1로 변경을 시켜준다. 이 작업을 while문을 통해 반복하되 더이상 녹일 치즈가 없을 때 (meltingQueue.isEmpty() == true일 경우) 종료한다.

 

 

 

 

바깥 공기와 내부 공간을 분리해야한다는 접근까지는 잘 했는데 그 이후 어떻게 탐색할 것인지까지는 생각하지 못해 자력으로 풀지 못해 아쉬웠다. 다음에 다시 한 번 풀어봐도 좋을 문제인 것 같다.

 

[참고] https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221041082692&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

소스 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int row;
    private static int col;
    private static int[][] board;
    private static boolean[][] visited;
    private static Queue<Point> meltingQueue = new LinkedList<>();
    private static int day = 0;
    private static int pre = 0;
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        row = scanner.nextInt();
        col = scanner.nextInt();

        board = new int[row + 1][col + 1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                board[i][j] = scanner.nextInt();
            }
        }

        while (true) {
            visited = new boolean[row + 1][col + 1];
            
            // 바깥 공기를 -1로 바꾼다.
            checkOutsideAir();

            // 치즈의 가장자리 구역을 찾고, meltingQueue에 저장
            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    if (board[i][j] == 1 && isEdge(i, j)) {
                        bfs(i, j);
                    }
                }
            }

            // 녹을 치즈가 더이상 없는 경우 종료
            if (meltingQueue.isEmpty()) break;

            // 모든 치즈가 녹기 한 시간 전 남은 치즈적 면 == 마지막으로 녹아야할 치즈 면
            pre = meltingQueue.size();

			// meltingQueue에 있는 치즈 녹이기
            while (!meltingQueue.isEmpty()) {
                Point point = meltingQueue.poll();
                board[point.x][point.y] = -1;
            }

            // 날짜++
            day++;
        }

        System.out.println(day + " " + pre);
    }

    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            if (isEdge(point.x, point.y)) {
                board[point.x][point.y] = 2;
                meltingQueue.add(new Point(point.x, point.y));
            }

            for (int i = 0; i < 4; i++) {
                int newX = point.x + dx[i];
                int newY = point.y + dy[i];

                if (isInArea(newX, newY) && board[newX][newY] == 1 && !visited[newX][newY]) {
                    queue.add(new Point(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
    }

    private static boolean isEdge(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (board[newX][newY] == -1) {
                return true;
            }
        }

        return false;
    }

    private static void checkOutsideAir() {
        Queue<Point> queue = new LinkedList<>();
        boolean[][] visitedAir = new boolean[row + 1][col + 1];

        queue.add(new Point(1, 1));
        board[1][1] = -1;
        visitedAir[1][1] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newX = point.x + dx[i];
                int newY = point.y + dy[i];

                if (isInArea(newX, newY) && !visitedAir[newX][newY] && board[newX][newY] <= 0) {
                    board[newX][newY] = -1;
                    visitedAir[newX][newY] = true;
                    queue.add(new Point(newX, newY));
                }
            }
        }
    }

    private static boolean isInArea(int x, int y) {
        return x > 0 && x <= row && y > 0 && y <= col;
    }

    static class Point {
        private int x;
        private int y;

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