[27737] 버섯 농장

🔗 문제 링크

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

🔍 문제 설명

농부 해강이는
$N \times N$ 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있다.

해강이는
$M$개의 버섯 포자를 가지고 있다. 버섯 포자는 버섯이 자랄 수 있는 칸에만 심을 수 있다.

각 버섯 포자는 포자가 심어진 칸을 포함해 최대
$K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결된 칸은 상하좌우로 적어도 한 변을 공유하는 칸들의 집합이라고 정의한다.

또한 한 칸에 버섯 포자를 여러 개 겹쳐서 심을 수 있으며, 만약
$x$개의 버섯 포자를 겹쳐 심으면 포자가 심어진 칸을 포함해 최대
$x \times K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯이 자란다.

해강이는 버섯 포자를 심을 때 최소 개수로만 심으려고 한다. 해강이가 농사가 가능할지 판단하고, 농사가 가능하다면 남은 버섯 포자의 개수를 출력하시오.

버섯 포자를 하나라도 사용하고 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능하다고 정의한다.

⚠️ 제한사항

• 첫 번째 줄에 $N$, $M$, $K$ 가 공백으로 구분되어 주어진다.

• 두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다.

• 버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸은 1로 주어진다.

• 만약 버섯 농사가 불가능하면 IMPOSSIBLE을 출력한다.

• 버섯 농사가 가능하다면, POSSIBLE을 출력하고 다음 줄에 남은 버섯 포자의 개수를 출력한다.
  
  

  ---

🗝 풀이 (언어 : Java)

BFS로 풀었다. k 부분 처리를 나중에해야 메모리 초과 채점에 통과했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer nmk = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(nmk.nextToken());
        int m = Integer.parseInt(nmk.nextToken());
        int k = Integer.parseInt(nmk.nextToken());
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer land = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(land.nextToken());
            }
        }
        solution(matrix, m, k);
    }

    public static void solution(int[][] matrix, int m, int k) {
        int used = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j] == 0) {
                    int result = bfs(matrix, new int[] {i, j});
                    int count = result / k;
                    if (result % k != 0) {
                        count++;
                    }
                    used += count;
                }
            }
        }
        if (used == 0 || used > m) {
            System.out.println("IMPOSSIBLE");
            return;
        }
        System.out.println("POSSIBLE");
        System.out.println(m - used);
    }

    public static int bfs(int[][] matrix, int[] current) {
        Queue<int[]> queue = new LinkedList<>() {{
            add(current);
        }};
        matrix[current[0]][current[1]] = 1;
        int count = 1;
        while (!queue.isEmpty()) {
            int[] next = queue.poll();
            for (int[] d : dir) {
                if (next[0] + d[0] >= 0
                        && next[1] + d[1] >= 0
                        && next[0] + d[0] < matrix.length
                        && next[1] + d[1] < matrix.length
                        && matrix[next[0] + d[0]][next[1] + d[1]] == 0) {
                    matrix[next[0] + d[0]][next[1] + d[1]] = 1;
                    count++;
                    queue.add(new int[] {next[0] + d[0], next[1] + d[1]});
                }
            }
        }
        return count;
    }

}