[백준][자바] 27737 - 버섯농장 - BFS(완전탐색)

📌 문제

백준 | 버섯농장 | SILVER 1 | 완전탐색

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

 

 

📌 문제 탐색하기

• N * N 칸으로 이루어진 나무판
  • 버섯이 자랄 수 있는 칸
  • 버섯이 자랄 수 없는 칸
• M개의 버섯포자 (자랄 수 있는 칸에 배치)
• 포자가 심어진 칸을 포함해 최대 K개의 연결된 칸에 버섯이 자람
  • 상하좌우로 적어도 한 변을 공유하는 칸들
• 한 칸에 여러개 겹쳐서 심을 수 있음
• ex) x개의 버섯 포자 겹쳐서 = x * K개의 연결된 칸에 버섯

 

• 입력 : N(크기), M(버섯 포자 개수), K(연결)
  • 0 : 버섯 자랄 수 O
  • 1 : 버섯 자랄수 X
• 출력 : 농사가 가능할 경우, 남은 버섯 포자의 개수
  • 농사 가능 = 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능

 

 

 

📌 알고리즘

나무 판에서 ‘버섯이 자랄 수 있는’ 공간들을 연결하는 것이 핵심이므로, 완전탐색(BFS)을 통해 방문하는 것이 적합하다고 판단했습니다.

 

 

📌 코드 설계하기

1. N,M,K 입력
2. 배열 입력 초기화 (grid)
3. BFS 로직 작성
   1. Queue를 활용하여 상하좌우 이동한 노드들 연결
   2. 다만, 이동 시 grid를 벗어나지 않는지 및 재방문하지 않는 노드인지 확인 필요
   3. 문제에서 땅의 크기를 k로 나눠서 이를 ‘올림’한 값을 M에서 제거하므로 땅의 크기를 return (size)
   ex) 예를들어 땅의 크기 4, K 3이면 최소 2개의 포자가 필요 : 4/3 = 1.3333 (올림 → 2)
   
   
4. 반환받은 size를 바탕으로 최소 1개의 포자사용 여부 파악
   1. 사용 시, possible & m - size
   2. 사용 x , impossible

 

 

📌 시도 회차 수정

1회차

• 문제에서 '버섯 포자를 하나라도 사용하고' 라는 조건이 있었는데 이 조건을 놓쳐서 틀렸음을 확인함
• ⇒ flag를 추가해서 포자 사용 여부를 체크해야한다.

###틀린 1차 코드###
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

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

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && visited[i][j] == 0) {
                    double size = bfs(i, j, visited, grid);
                    size = (int) Math.ceil(size / k);
                    m -= size;
                }
            }
        }

        if(m >=0){
            System.out.println("POSSIBLE");
            System.out.println(m);
        } else {
            System.out.println("IMPOSSIBLE");
        }
    }

    public static double bfs(int x, int y, int[][] visited, int[][] grid) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x,y));
        visited[x][y] = 1;

        int size = 1;
        while(!queue.isEmpty()){
            Point cur = queue.poll();

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

                if(canGo(nx, ny, grid, visited)){
                    visited[nx][ny] = 1;
                    queue.offer(new Point(nx, ny));
                    size++;
                }
            }
        }
        return size;
    }

    public static boolean canGo(int x, int y, int[][] grid, int[][] visited){
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length){
            return false;
        } else if(grid[x][y] == 1 || visited[x][y] == 1){
            return false;
        }
        return true;
    }
}


class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

📌 정답 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

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

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

        boolean isChanged = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && visited[i][j] == 0) {
                    double size = bfs(i, j, visited, grid);
                    size = (int) Math.ceil(size / k);
                    m -= size;
                    isChanged = true;
                }
            }
        }

        if(isChanged && m >=0){
            System.out.println("POSSIBLE");
            System.out.println(m);
        } else {
            System.out.println("IMPOSSIBLE");
        }
    }

    public static double bfs(int x, int y, int[][] visited, int[][] grid) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x,y));
        visited[x][y] = 1;

        int size = 1;
        while(!queue.isEmpty()){
            Point cur = queue.poll();

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

                if(canGo(nx, ny, grid, visited)){
                    visited[nx][ny] = 1;
                    queue.offer(new Point(nx, ny));
                    size++;
                }
            }
        }
        return size;
    }

    public static boolean canGo(int x, int y, int[][] grid, int[][] visited){
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length){
            return false;
        } else if(grid[x][y] == 1 || visited[x][y] == 1){
            return false;
        }
        return true;
    }
}


class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

최근에 bfs 문제를 계속 풀고 있는데, 문제는 정형화되어 있으므로 반복된 풀이가 필요할 듯 하다.

다만, 이번 문제에서 '1번 이상의 사용' 과 같은 트릭이 있을 수 있으니, 문제를 구체적으로 읽는 연습을 통해 실수를 줄이는 것이 필요할 것 같다. 👍⭐