[DFS] 백준 27737 버섯 농장(서브태스크) JAVA

[문제출처 | https://www.acmicpc.net/problem/27737 ]

---

💭접근 방식

처음 문제를 읽었을 땐 이전에 풀었던 섬의 개수, 토마토와 비슷한 느낌을 받았다.
전형적인 DFS, BFS 문제로 구역을 탐색하며 흔적을 남기고 그때마다 카운팅한 어떤 결과물을 도출하는 것.

문제 내용 중 한 칸에 여러 개 포자를 겹쳐 심을 경우 범위가 더 늘어난다는 예시 이미지를 보고 순간 생각이 많아졌는데..
(BFS에 DFS까지 합쳐야 하는 문제인가? 해당 칸에 1개만 심을 경우, 2개 심을 경우, X개 심을 경우 퍼져 나갈 수 있는 칸은 X * K 개니까.. 헉 그럼 어떻게 풀어야하지? \(°_o)/ )
이러다 날 샌다.. 일단 겹쳐 심는 경우는 제쳐두고 하나씩 심는 경우에서 풀어나가 보자.

시작은 섬의 개수 풀이랑 비슷하게 구역을 구하는 식으로 접근했다.
1. 버섯이 자랄 수 있는 인접한 칸들의 덩어리=구역(area)을 탐색한다.
2. 각 구역들의 칸 수를 저장한다.
3. 구역별 칸 수를 연결 가능한 칸 수(K)로 나눈 값에 따라 필요한 포자 수의 합계를 구한다.
4 -1. 총 필요 포자 수(needs)가 가지고 있는 포자 수(M)보다 같거나 작으면 농사가 가능하고, 그 차를 출력한다.
4 -2. 그렇지 않을 경우 농사는 불가능하다.

탐색은 DFS 알고리즘으로 선택했다.
M, K 최대값이 컸지만 맵 사이즈인 N이 100이라 괜찮지 않을까? 하는 생각으로

아참, 문제 내용 중 '버섯 포자를 하나라도 사용하고' 라는 조건을 유의해야 한다.
버섯 포자를 하나도 사용하지 못하는 경우가 있다는 뜻이다.

---

📝풀이 과정

변수

• int area[N * N / 2 + 2] : 인접한 칸들의 구역 관리, 최악의 경우 각 한 칸씩만 가능한 map이 주어졌을 때이고(N*N/2 + 1) 1번 인덱스부터 사용할거라 1을 더해줬다.
  근데 N의 값이 그리 크지 않고 메모리를 넉넉하게 준 문제이므로 N * N 에 1번 인덱스용 +1 로 할당해도 괜찮다. (N*N+1)
• cnt : 구역의 개수=인덱스
• needs : 총 필요 포자 수

자원 재정의

탐색을 하며 map 원본에 구역별 인덱스를 덮어 씌울거라 버섯이 자랄 수 없는 칸 '1'을 '-1'로 재정의하여 입력을 받았다.

주요 풀이

• map을 돌며 DFS를 태울 때 cnt가 0에서 시작하기 때문에 ++cnt 또는 dfs 호출 앞에서 cnt++ 을 해주고 보내야 한다.
  cnt 가 0인 경우를 걸러줘야 함. dfs를 태우지 못한 즉, 버섯이 자랄 수 있는 칸이 없는 map일 때를 유의.
• 각 구역 별 칸 수(area[i])가 연결 가능한 칸 수(K)로 나눠지면 그 몫만큼만 필요하고 그렇지 않을 경우 몫에서 하나 더 필요하다.
  area[i] % K == 0 ? area[i] / K : area[i] / K + 1
• 농사가 가능한 경우는 '최소 하나라도 사용' 하고 '주어진 포자 수가 필요한 포자수 총합보다 크거나 같을' 때다.
  cnt > 0 && M >= needs

---

📚참고 자료

[백준,유기농배추| https://www.acmicpc.net/problem/1012 ]

[백준,섬의 개수| https://www.acmicpc.net/problem/4963 ]

---

---

💡정답 코드

결과| 100점, 메모리 16972KB, 시간 136ms

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

public class Main {

    static int map[][], N, M, K, area[];
    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()); // map 크기
        M = Integer.parseInt(st.nextToken()); // 포자 수
        K = Integer.parseInt(st.nextToken()); // 가능한 연결 칸 수

        map = new int[N][N];
        area = new int[N*N/2 + 2];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()) * -1;
            }
        }

        int cnt = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) {
                    dfs(i, j, ++cnt);
                }
            }
        }

        int needs = 0;
        for(int i = 1; i < area.length; i++) {
            if(area[i] > 0) {
                needs += (area[i] % K == 0 ? area[i] / K : area[i] / K + 1);
            }
        }

        if(cnt > 0 && M >= needs) {
            System.out.printf("%s\n%d", "POSSIBLE", M - needs);
        } else {
            System.out.println("IMPOSSIBLE");
        }
    }

    static int dr[] = {-1, 1, 0, 0};
    static int dc[] = {0, 0, -1, 1};
    private static void dfs(int r, int c, int idx) {
        map[r][c] = idx;
        area[idx]++;

        for(int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if(nr < 0 || nc < 0 || nr >= N || nc >= N)
                continue;
            if(map[nr][nc] == 0) {
                dfs(nr, nc, idx);
            }
        }
    }
}

---