[백준] 27737번 - 버섯 농장 java

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

 

난이도 : S1

Tag : BFS/DFS

풀이 일자 : 2025-03-05

---

문제 탐색하기

N: 정사각형 버섯농장 한 변의 나무판 길이 (1 <= N <= 100)

M: 버섯 포자 개수 (0 <= M <= 1,000,000)

K: 하나의 버섯포자가 자라게 할 수 있는 최대 버섯 수 (상, 하, 좌, 우) (1 <= K <= 1억)

 

0 : 버섯이 자랄 수 있는 칸

1 : 버섯이 자랄 수 없는 칸

 

조건 :

• 한 칸에 여러 개의 버섯 포자를 겹쳐 심을 수 있다.
  • 이때 자랄 수 있는 최대 버섯 수는 x * K

농사가 가능한 조건 : 

• 버섯 포자를 하나라도 사용해야 합니다.
• 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자라야 합니다.

즉, 버섯이 자랄 수 있는 땅을 모두 덮을 수 있는 최소 포자 개수를 구하고, 남은 포자의 개수를 출력하는 것이 핵심입니다.

가능한 시간복잡도

• 농장의 최대 크기는 100 x 100 = 10,000 이므로 모든 칸을 탐색하는 시간 복잡도는 O(N^2) = O(10,000) 입니다.
• K의 값이 최대 10^8이지만, 실제 연산은 O(N^2) 이내에서 처리해야 합니다.
• 따라서, 탐색 알고리즘을 BFS로 사용하여 연산을 최적화해야 합니다.
• DFS는 깊이 우선 탐색이므로, 재귀 호출이 많아지면 스택 오버플로우 위험이 있습니다.

알고리즘 선택

시간 효율이 중요하므로 BFS를 사용하겠습니다.

• BFS는 너비 우선 탐색으로 각 연결된 구역을 한 번씩만 방문하여 전체 영역을 빠르게 탐색할 수 있습니다.
• 각 구역을 BFS로 탐색하여 연결된 0의 개수를 구하고, K로 나누어 필요한 최소 포자 개수를 계산합니다.
• 왜 BFS일까?
  • DFS는 재귀 호출이 많아지면 비효율적이고, 시간 초과 가능성이 높습니다.
  • BFS는 큐를 이용해 한 번만 탐색하므로, 메모리와 시간 측면에서 더 효율적입니다.

---

코드 설계하기

1. 값을 입력받아 각 버섯농장의 크기와 버섯포자의 수, 최대로 자라는 버섯수를 입력받습니다.
2. BFS 탐색을 통해 연결된 땅의 개수 계산합니다.
   • visited[][]를 활용하여 한 번 방문한 땅은 다시 방문하지 않도록 설정.
   • 큐(Queue<int[]>)를 사용해 BFS 진행.
   • 상하좌우 탐색을 하며 0이 연결된 개수를 areaSize에 저장.
3. 하나의 연결된 땅의 계산이 끝나면 포자의 수를 계산합니다.
   • 각 연결된 영역의 크기를 K로 나눈 후, 필요한 최소 포자 개수를 계산.
   • 남은 포자 개수를 갱신 (M -= neededSpore).
4. 탐색 도중 남은 포자가 부족하거나, 탐색이 끝난 후에도 포자가 하나도 사용되지 않았다면 "IMPOSSIBLE"을 출력합니다. 
5. 농사가 가능할경우 "POSSIBLE"을 출력하고, 남은 포자 개수를 출력합니다.

 

시도 회차 별 수정사항

1차 시도

• 부분 점수 10점을 받음. (98%에서 계속 틀림)
• 원인을 찾다가 BFS 탐색 중 포자를 모두 사용했을 때도 "IMPOSSIBLE"로 판단하는 오류를 발견.
• 처음엔 포자가 부족한 경우 return 0으로 바로 "IMPOSSIBLE"을 출력했는데, 포자를 정확히 다 쓰고 끝나는 경우를 고려하지 않음.
• 해결책: 남은 포자 개수를 그대로 반환하고, 남은 포자가 음수이거나 하나도 사용되지 않은 경우 "IMPOSSIBLE" 처리.

2차 시도?

• 정답이 나왔지만, 실행 시간이 320ms로 다소 느렸음.
• 원인을 분석하니 Scanner가 입력 속도를 크게 저하시킴.
• BufferedReader + StringTokenizer로 바꾼 후 실행 시간을 줄이는 데 성공.
• 최적화 결과, 실행 시간이 약 1/2로 단축됨.

//처음 입력방식
Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        mushroom = new int[n][n];
        visited = new boolean[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) mushroom[i][j] = sc.nextInt();
        }


//바꾼 후 입력방식
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        mushroom = new int[n][n];
        visited = new boolean[n][n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                mushroom[i][j] = Integer.parseInt(st.nextToken());
            }
        }

 

실행시간과 메모리가 확 줄어들었다!

 

 

---

정답코드

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

class Main {
    public static int n, m, k;
    public static int[][] mushroom;
    public static boolean[][] visited;
    
    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());
        k = Integer.parseInt(st.nextToken());

        mushroom = new int[n][n];
        visited = new boolean[n][n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                mushroom[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int ans = BFS();

        if(ans < 0 || ans == m) {
            System.out.println("IMPOSSIBLE");   
        }
        else {
            System.out.println("POSSIBLE");
            System.out.println(ans);
        } 
    }
    public static int BFS(){
        Queue<int[]> q = new LinkedList<>();
        int dy[] = {0,0,1,-1};
        int dx[] = {1,-1,0,0};
        int remainedSpore = m;
        int areaSize = 0;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(visited[i][j] || mushroom[i][j] == 1) continue;
                areaSize = 1;
                visited[i][j] = true;
                q.add(new int[] {i, j});

                while(!q.isEmpty()){
                    int[] curr = q.poll();
                    int y = curr[0];
                    int x = curr[1];

                    for(int dir=0; dir<4; dir++){
                        int ny = y + dy[dir];
                        int nx = x + dx[dir];

                        if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                        if(visited[ny][nx] || mushroom[ny][nx] == 1) continue;

                        visited[ny][nx] = true;
                        q.add(new int[] {ny, nx});
                        areaSize++;
                    }
                }
                int neededSpore = (areaSize/k);
                if(areaSize%k != 0) neededSpore++;

                remainedSpore-=neededSpore;
                if(remainedSpore < 0) break;
            }
        }
        return remainedSpore;
    }
}