문제 탐색하기

입력 자료 정리하기

1. N은 버섯 농장의 가로 세로 길이이다
2. M은 심을 수 있는 버섯의 개수다
3. K는 하나의 버섯이 줄 수 있는 영향력이다
4. 이후 들어오는 값은 N X N 크기의 배열의 각 인덱스 원소이다.
   이때 0은 버섯을 심을 수 있는 곳으로 탐색체크의 대상이 되며,
   1은 버섯을 심을 수 없는 곳으로 탐색하지 않는 곳이다.

해결방법 추론

1. 버섯의 포자가 전파되는 모습이 BFS의 탐색 방식과 똑같이 보였다
2. 따라서 BFS 탐색 방법으로 풀어야겠다고 생각했는데... 문제를 읽다보니 살짝 의구심이 들었다
3. 그림을 보면 중복 위치에 버섯을 여러개 심어서 포자를 퍼트릴 수 있는 범위를 넓힐 수 있다
4. 그렇다면 방문체크를 하지 않고, 중복해서 심는 경우도 모두 고려해야할까? 라는 의문이 들었다
5. 출력값이 버섯을 심는 위치를 최소한으로 한다면 굉장히 까다로운 문제였을것이다
6. 하지만 다행히도 버섯의 최소 사용개수를 출력하는 문제였고,
   굳이 중복위치에 심지 않고 BFS 탐색 방법대로 포자를 퍼트려도 해결할 수 있겠다고 생각하였다
7. 문제에서 예외상황을 몇가지 주었다. 이 경우에는 불가능하다는 출력을 해야한다
8. 예외상황은 총 3가지이다.
   8-1. m이 0인 경우
   8-2. 필요한 버섯의 개수가 m보다 큰 경우
   8-3. 버섯을 한번도 사용하지 않은 경우
9. 위와 같은 예외 상황을 제외하고는 BFS 탐색 결과를 출력하면 될 것이다
10. 탐색하면서 사용하게 되는 버섯은 초기 입력값인 m의 값을 감소시켜서 관리할 것이다
11. 이렇게 한다면 아직 사용하지 않은 버섯의 개수만 남으므로 그대로 정답으로 사용하면 될 것이다

시간복잡도 계산

1. 주어진 배열을 모두 탐색해야하므로 n x n만큼의 연산이 발생한다
2. BFS 탐색에서는 상하좌우 탐색에서 4번 연산이 발생한다.
   그리고 최대 탐색할 수 있는 경우는 동일하게 n x n이다
3. 따라서 최대 나올 수 있는 연산은 n x n x 4이고, 상수는 제외하고 생각해서
   시간복잡도는 O(n^2)이 된다
4. 따라서 시간제한안에 BFS 탐색으로 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. n,m,k는 변수로 값을 관리한다.
2. 이후 들어오는 버섯농장 땅들의 상태는 int형 타입의 2차원 배열에 보관한다
   이때 크기는 n x n이다
3. BFS 탐색을 위한 방문체크 배열을 동일하게 미리 초기화하며,
   이어서 4방 탐새긍ㄹ 위한 변수도 하나 준비한다

BFS 탐색 설계

1. n x n만큼 순회하면서, 현재 원소의 값이 0인경우와 미방문한 경우 BFS탐색을 진행한다
2. BFS 탐색 전 현재 남은 버섯의 개수가 0인 경우는 불가능을 확인하기 위한 임시 변수를 바꿔주고
   순회를 탈출한다
3. BFS 탐색에서는 각 탐색마다 개수를 세어주어야한다.
   이때 개수는 연결된 버섯을 심을 수 있는 구역이다
4. 해당되는 모든 구역을 확인한 뒤에 버섯 하나당 영향력인 k만큼 나눈 몫만큼 빼주고
   나머지가 존재하는 경우 버섯을 하나 더 사용해야하므로 개수를 하나 더 추가로 빼준다
5. 4번 과정 진행전 한가지 확인해야할 것이 있는데,
   현재 개수를 센 값이 m x k보다 큰지를 확인해야한다.
   m x k는 현재 남은 버섯들이 포자를 퍼트릴 수 있는 범위를 말하므로,
   현재 탐색한 개수가 그 범위보다 많다면 정답이 될 수 없기 때문이다
6. 5번 검증을 한번 거친 뒤 4번을 실행한다면 탐색하면서 사용한 버섯의 개수를 참가하면서
   탐색을 진행할 수 있다

출력 설계

예외항목에 대한 출력

1. m이 0인경우와 isOk가 false인 경우는 IMPOSSIBLE을 출력한다
2. 이때 isOk가 false인 경우는 다음과 같다
   2-1. m이 0인데 아직 탐색해야하는 경우가 더 남은 경우
   2-2. BFS 탐색전 미리 만들어둔 m의 초기값을 관리하는 chk와 m이 같은 경우
3. 2-2의 경우는 버섯 포자를 한번더 심지 않은 경우이다

정답에 대한 출력

1. 그 외의 모든 경우에 대해서는 POSSIBLE을 출력한다
2. 이어서 현재 남은 버섯의 개수인 m을 출력하면 정답이 될텐데...

시도회차 수정

1~2회차 시도 실패

1. 1~2회차 시도 모두 52%에서 실패가 발생하였다
2. 두 코드 모두 비슷하며, count의 증가 위치를 조금 바꾼 것일 뿐
   전체적인 흐름은 크게 변하는게 없어 통합하여 정리하였다

탐색 방법 변경

1. 사실 설계하면서 count > m x k부분이 정말 수학적으로 맞는 식일까라는 의문이 들었다
2. 그리고 isOk의 사용이 너무 더럽다는 생각도 하였다
3. 과연 이 방식이 맞을까 라는 생각을 하였고, 차라리 bfs에 반환타입 int를 붙이는 것으로
   바꿔보자는 생각을 하게 되었다
4. 마지막으로 버섯의 사용 여부를 체크하기 위해 chk 변수를 만들어서 BFS 탐색전 상태를
   관리하는 코드도 바꿔야겠다고 생각하였다
5. BFS 탐색의 방법과 그 결과를 관리하는 방법을 바꾼다면,
   정답에 의문이 든 부분도 해결하고 더러운 코드도 깔끔하게 해결할 수 있을 것이다
6. 이전에는 m의 개수가 0개이면 모든 탐색을 멈췄는데, 이제는 그냥 모든 경우를 다 세어준다
7. 이를 위해 ans 변수를 하나 선언하고 반환값으로 BFS 결과를 받아 더해준다
8. BFS에서 계산 방법은 동일한다.
   단 count > m x k인 경우를 제한하는 코드는 이제 불필요해졌기에 지워준다
9. 이제 chk 변수 사용 없이 ans가 0이면 자동으로 버섯을 사용하지 않은 것이 된다
10. 또한 ans가 m보다 크다면 주어진 버섯보다 많이 사용해야하므로 불가능한 경우가 된다.
11. 또한 m-ans를 한다면 남은 버섯의 개수도 알 수 있을 것이다.

3회차 시도 성공

1. 위 방법으로 바꿔서 다시 시도했을 때, 바로 성공하였다
2. 문제가 되는 부분은 count > m x k가 아니었을까 싶다
3. 왜 문제가 되었을까 생각을 해보니
   count % k인 경우 count가 k를 못 채우더라도 버섯을 하나 사용해야하는 경우가 발생하여
   반례가 생기기 때문이다
4. 따라서 위와 같이 탐색 방법을 조금 변경시킨다면 코드도 깔끔해지고
   원하는 결과도 찾아 정답이 된다.

정답 코드

(1~2회차 시도 실패)

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


public class Main {

    static int[][] arr;
    static boolean[][] visited;
    static int m;
    static int k;
    static int[] dy = {0,0,-1,1};
    static int[] dx = {-1,1,0,0};
    static boolean isOk = true;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        if (m == 0) {
            bw.write("IMPOSSIBLE");
        }else{
            int chk = m;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(arr[i][j] == 0 && !visited[i][j]){
                        if(m == 0){
                            isOk = false;
                            break;
                        }
                        bfs(n, i, j);

                    }
                    if(!isOk){
                        break;
                    }
                }
                if(!isOk){
                    break;
                }
            }

            if(chk == m){
                isOk = false;
            }

            if(!isOk){
                bw.write("IMPOSSIBLE");
            }else{
                bw.write("POSSIBLE\n");
                bw.write(m+"");
            }

        }

        br.close();
        bw.close();
    }

    private static void bfs(int n, int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {y,x});
        visited[y][x] = true;
        int count = 0;
        while(!q.isEmpty()){
            int[] tmp = q.poll();

            count++;

            for (int i = 0; i < 4; i++) {
                int ny = tmp[0] + dy[i];
                int nx = tmp[1] + dx[i];
                if(ny >= 0 && nx >=0 && ny < n && nx < n && !visited[ny][nx] && arr[ny][nx] == 0){
                    q.add(new int[]{ny,nx});
                    visited[ny][nx] = true;
                }
            }
        }

        if(count > m * k){
            isOk = false;
            return;
        }
        m -= (count / k);
        m -= (count % k > 0 ? 1 : 0);
    }

}

(3회차 시도 성공)

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

public class Main {

    static int[][] arr;
    static boolean[][] visited;
    static int m;
    static int k;
    static int[] dy = {0,0,-1,1};
    static int[] dx = {-1,1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        if (m == 0) {
            bw.write("IMPOSSIBLE");
        }else{
            int ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(arr[i][j] == 0 && !visited[i][j]){
                        ans += bfs(n, i, j);
                    }
                }
            }

            if(ans > m || ans == 0 ){
                bw.write("IMPOSSIBLE");
            }else{
                bw.write("POSSIBLE\n");
                bw.write((m-ans)+"");
            }

        }

        br.close();
        bw.close();
    }

    private static int bfs(int n, int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {y,x});
        visited[y][x] = true;
        int count = 0;
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            count++;

            for (int i = 0; i < 4; i++) {
                int ny = tmp[0] + dy[i];
                int nx = tmp[1] + dx[i];
                if(ny >= 0 && nx >=0 && ny < n && nx < n && !visited[ny][nx] && arr[ny][nx] == 0){
                    q.add(new int[]{ny,nx});
                    visited[ny][nx] = true;
                }
            }
        }


        int res = count / k;
        res += (count % k > 0 ? 1 : 0);
        return res;
    }

}

문제 링크

27737번 - 버섯 농장