[백준/Java] 27737번 : 버섯 농장

✏️ 문제 탐색

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

 

이번 문제는 설명이 길어서 조건을 파악하기 쉽게 요약해보았다.

• NxN 나무판에 M개의 버섯 포자를 심는다.
• 버섯이 자랄 수 있는 칸과 자랄 수 없는 칸이 있는데, 자랄 수 있는 칸에만 심을 수 있다.
• 심어진 버섯 포자는 심어진 칸을 포함해 K개의 상하좌우로 연결된 칸에 자란다.
• 한 칸에 x개를 겹쳐서 심는다면 심어진 칸을 포함해 K*x개의 상하좌우로 연결된 칸에 자란다.
• M개의 버섯 포자 중 최소 개수를 사용하여 농사가 가능한지 불가능한지 출력하라.
• 농사가 가능하다는 것의 의미는 다음과 같다.
  • 버섯 포자를 하나라도 사용하였음
  • 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자람
• 농사가 가능하다면 POSSIBLE을 출력하고, 다음 줄에 남은 버섯 포자의 개수를 출력한다.
• 농사가 불가능하다면 IMPOSSIBLE을 출력한다.

---

아래 그림은 문제에 제시된 예시이다.

출처: 백준 27737번

 

• 왼쪽 : K=4로 주어졌고 포자를 1개 심었으므로 심은 칸을 포함해 4칸에 버섯이 자랐다.
• 오른쪽 : K=4로 주어졌고 포자를 겹쳐서 3개 심었으므로 심은 칸을 포함해 4*3=12칸에 버섯이 자랐다.

 

출처 : 백준 27737번

• 왼쪽 : K=10으로 주어졌고 포자를 1개 심었으므로 심은 칸을 포함해 10칸에 버섯이 자랐다.
• 오른쪽 : K=10으로 주어졌고 포자를 3개 심었으므로 심은 칸을 포함해 10*3=30칸에 버섯이 자라야 하는데, 자랄 수 있는 칸이 17개 뿐이므로 총 17칸에 버섯이 자랐다.

 

✏️ 구현 아이디어 / 알고리즘 

5 100 1
1 1 1 0 0
1 0 1 0 0
0 0 1 1 1
1 1 0 0 0
0 1 1 0 1

1. 시작 지점을 (0,0)으로 두고 NxN 나무판의 칸을 하나씩 탐색한다.
2. 버섯이 자랄 수 있는 칸을 발견하면 상하좌우로 연결된 자랄 수 있는 칸의 수를 센다.
   -> 이 때, 한 지점에서 상하좌우를 탐색하며 연결된 모든 노드를 방문해야 하므로 DFS 또는 BFS 그래프 탐색을 사용하면 된다. 아래 💡글을 참고하길 바란다.
   -> (0, 3)위치에서 0 즉 버섯이 자랄 수 있는 칸을 발견했으므로, 그래프 탐색을 시작하여 상하좌우로 연결된 0들을 모두 세고 돌아온다.
3. 연결된 칸의 수를 K로 나눈 후 소수점을 올림하여 최소 몇 개의 포자를 심어야 칸을 버섯으로 다 채울 수 있는지 구한다.
   -> (0, 3)에서 탐색한 버섯이 자랄 수 있는 칸의 개수는 4이다. K=1 포자를 한 개 심으면 1개씩 자라므로, 4를 1로 나눈다. 이 구간에 모두 버섯이 자라게 하려면 포자를 최소 4개 심어야 한다.
   -> 총 포자 수 M에서 4를 뺀다.
4. 1~3 과정을 나무판을 모두 방문할 때까지 반복

---

💡 그래프 탐색과 DFS BFS 선택 방법

1) 그래프 탐색이란

그래프는 노드와 노드들을 연결하는 간선으로 이루어진 자료구조이다. 그래프의 모든 노드들을 차례로 한 번씩 방문해야할 때 DFS, BFS가 쓰인다. 

 

2) DFS BFS 선택 방법

2-1) 단순히 모든 노드를 방문하는 것이 중요한 문제인 경우 DFS BFS 중 어떤 것을 선택 해도 상관 없음

 

2-2) 방문 경로 추적할 때는 DFS, 최단거리를 구할 때는 BFS

DFS는 재귀나 스택으로 연쇄적으로 연결된 노드를 탐색한다. 따라서 방문 경로를 추적하거나 경로별 특징을 저장해야할 때 주로 사용한다. 

반면 BFS는 현재 노드와 가까운 곳을 먼저 탐색하고, 경로의 개념이 없다. 따라서 미로찾기 등 최단 거리를 측정해야할 때 주로 사용된다.

 

2-3) 그래프 규모가 크다면 DFS

DFS는 현재 탐색 중인 경로만 스택에 저장하지만 BFS는 탐색 중에 현재 노드와 인접한 모든 노드를 큐에 저장해야 하므로 공간 효율성이 좋지 않다. 또한 큰 규모의 그래프에서는 목표 노드가 멀리 있을 수 있는데 너비 우선 탐색을 하는 BFS보다 깊이 우선 탐색을 하는 DFS가 멀리 있는 노드에 더 빨리 도달할 수 있다. 따라서 시간 효율성 측면에서도 DFS가 유리하다.

 

👉🏻 내 문제에 적용

• 이 문제는 단순히 연결된 모든 노드를 방문하면 되는 문제임
• 그래프 규모는 최대 10,000개의 노드로 이루어져있으므로 작은 편
• 경로를 추적하지 않아도 됨
• 둘 중 아무거나 사용해도 상관 없는 문제이다! 지난 시간에 BFS를 써봐서 DFS로 구현해보겠다.

✏️ 코드 설계

1. board[][]에 입력값을 받는다.
2. 아직 방문하지 않았고 값이 0이면 DFS 탐색을 시작한다.
3. DFS 탐색을 시작하기 전에 버섯이 자랄 수 있는 칸 개수를 새로 세기 위해 0으로 초기화한다.
4. DFS 과정
   
   1. 시작 위치를 방문 처리하고, 버섯이 자랄 수 있는 칸 개수를 하나 더한다. cnt++
   2. 상하좌우를 확인하며 아직 방문하지 않았고 값이 0이면 재귀호출한다.
5. DFS 탐색이 끝난 후 cnt를 K로 나누고 소수점을 올림하여 필요한 최소 포자 개수를 현재 남은 포자 개수 ans에서 뺀다.
6. 모든 노드 탐색이 끝난 후, 남은 포자 개수 ans가 음수거나 그대로이면 농사를 지을 수 없는 것이므로 IMPOSSIBLE을 출력
7. 그렇지 않으면 POSSIBLE과 남은 포자 개수를 출력

✏️ 시간 복잡도

주어진 입력 범위:

• 1 <= N <= 100
• 0 <= M <= 1,000,000
• 1 <= K <= 10^8
• N, M, K 는 모두 정수

시간 복잡도:

• NxN 나무판의 모든 노드를 방문한다.
• BFS/DFS 탐색 시 방문했던 곳은 다시 방문하지 않기 때문에 시간 복잡도는 O(N)
• 최대 100*100=10,000개의 노드를 방문하므로 제한 시간(2초) 안에 실행 가능하다.

✏️ 오답노트

버섯 포자를 하나라도 사용했는지 확인하는 조건을 넣지 않아서 틀렸다. 

if(ans<0) System.out.println("IMPOSSIBLE");

 

✏️ 정답코드

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

public class Main {
    static int N;
    static double M, K, cnt;
    static boolean[][] visited;
    static int[][] board;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    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 = Double.parseDouble(st.nextToken());
        K = Double.parseDouble(st.nextToken());

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

        //아직 방문하지 않았고 심을 수 있는 곳이면 탐색 시작
        visited = new boolean[N][N];
        double ans = M;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j] && board[i][j]==0){
                    cnt = 0;
                    dfs(i, j);
                    ans -= Math.ceil(cnt/K);
                }
            }
        }
		
        //버섯 포자가 부족하거나 하나도 심지 않았다면 농사 불가
        if(ans<0 || M==ans) System.out.println("IMPOSSIBLE");
        else System.out.println("POSSIBLE" + "\n" + (int)ans);

    }
    static void dfs(int x, int y){
        visited[x][y] = true;
        cnt++;

		//연결된 노드를 재귀 호출로 탐색
        for(int i=0; i<4; i++){
            int newX = x + dx[i];
            int newY = y + dy[i];

            if(newX<0 || newX>=N || newY<0 || newY>=N)
                continue;

            if(!visited[newX][newY] && board[newX][newY]==0)
                dfs(newX, newY);
        }
    }
}

✏️ Note

• 이번 포스팅을 정리하면서 DFS와 BFS를 언제 사용하는지와 그 이유는 무엇인지 확실히 알게 되었다.
• 백트래킹에 약한 나는 항상 재귀호출로 DFS를 구현하는 것에 대한 막연한 두려움이 있었는데 이 문제를 통해 조금 해소된 것 같다.