[백준] 2638번: 치즈 - JAVA

🔗 문제 링크

BOJ 2638번:치즈

2638번: 치즈

 

📝 풀이 과정

문제에서 외부 공기라는 개념이 존재하기 때문에, 가장자리는 항상 공기이므로 먼저 [0, 0]에서부터 BFS를 통해 0인 칸은 모두 10으로 변경해주었다. 이후 반복문을 돌며 치즈 칸에서 상하좌우 칸의 합이 20이상일 경우 외부 공기가 2칸 이상 존재한다는 것을 의미하므로 외부 공기로 변화시키는 BFS를 위한 Queue에 삽입한다.

 

반복문을 돌며 Queue 내부에 있는 값들을 10으로 변경하고 접촉한 공기 칸(0)은 모두 10으로 변경하며 반복문을 수행한 횟수를 세면 된다.

 

💻 코드

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};
        int N = sc.nextInt(), M = sc.nextInt();

        int[][] map = new int[N][M];
        int cheese = 0, ans = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1)
                    cheese++;
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});

        while (cheese > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                map[cur[0]][cur[1]] = 10;

                queue.add(cur);
            }

            while (!queue.isEmpty()) {
                int[] cur = queue.poll();

                for (int k = 0; k < 4; k++) {
                    int ny = cur[0] + dy[k];
                    int nx = cur[1] + dx[k];

                    if (ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx] != 0)
                        continue;

                    queue.add(new int[]{ny, nx});
                    map[ny][nx] = 10;
                }
            }

            for (int i = 1; i < N - 1; i++) {
                for (int j = 1; j < M - 1; j++)
                    if (map[i][j] == 1 && (map[i - 1][j] + map[i + 1][j] + map[i][j - 1] + map[i][j + 1]) >= 20) {
                        queue.add(new int[]{i, j});
                    }
            }
            cheese -= queue.size();
            ans++;
        }
        System.out.println(ans);

    }
}

 

📊 제출 결과