[BOJ/Silver 1] 백준 27737 버섯 농장(C++)

문제 링크

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

27737번: 버섯 농장

 

 

문제

농부 해강이는 N × N 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있다.

해강이는 M개의 버섯 포자를 가지고 있다. 버섯 포자는 버섯이 자랄 수 있는 칸에만 심을 수 있다.

각 버섯 포자는 포자가 심어진 칸을 포함해 최대 K개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결된 칸은 상하좌우로 적어도 한 변을 공유하는 칸들의 집합이라고 정의한다.

또한 한 칸에 버섯 포자를 여러 개 겹쳐서 심을 수 있으며, 만약 x개의 버섯 포자를 겹쳐 심으면 포자가 심어진 칸을 포함해 최대 x × K개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯이 자란다.

<그림 1>   K = 4일 때 버섯이 자라는 모습이다.

<그림 2>   K = 10일 때 버섯이 자라는 모습이다.

해강이는 버섯 포자를 심을 때 최소 개수로만 심으려고 한다. 해강이가 농사가 가능할지 판단하고, 농사가 가능하다면 남은 버섯 포자의 개수를 출력하시오.

버섯 포자를 하나라도 사용하고 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능하다고 정의한다.

입력

첫 번째 줄에 N, M, K가 공백으로 구분되어 주어진다.

두 번째 줄부터 N개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다.

버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸은 1로 주어진다.

출력

만약 버섯 농사가 불가능하면 IMPOSSIBLE을 출력한다.

버섯 농사가 가능하다면, POSSIBLE을 출력하고 다음 줄에 남은 버섯 포자의 개수를 출력한다.

제한

•  1 ≤ N ≤ 100
•  0 ≤ M ≤ 1,000,000
•  1 ≤ K ≤ 10^8
•  N, M, K는 모두 정수이다.

서브태스크

1	10	K=1
2	90	추가적인 제약 조건이 없다.

예제 입력 1

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

POSSIBLE
88

예제 입력 2

5 5 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

예제 출력 2

IMPOSSIBLE

예제 입력 3

5 100 3
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

예제 출력 3

POSSIBLE
94

해당 예제는 서브태스크 1에는 주어지지 않음을 유의하시오.

예제 입력 4

5 5 3
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

예제 출력 4

IMPOSSIBLE

해당 예제는 서브태스크 1에는 주어지지 않음을 유의하시오.

알고리즘 분류

• 그래프 탐색

풀이

BFS를 통해서 상하좌우로 연결된 구역의 칸 수를 구하고 그것을 K로 나눠서 해당 구역에 버섯이 자라게 하기 위해 필요한 포자의 개수를 구한다.

필요한 포자의 개수가 1개 이상이면, 모든 구역의 칸에 버섯이 자라는지를 파악한다. M개의 포자보다 많은 포자가 필요하다면 모든 구역의 칸에 버섯이 자라게 할 수 없기 때문에 IMPOSSIBLE을 출력한다. 최대 M개의 포자가 필요하다면 POSSIBLE을 출력하고 버섯을 자라게 한 후 남은 포자의 개수를 출력한다.

필요한 포자의 개수가 0개라면 IMPOSSIBLE을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 101
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, K;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = 0;

void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
}

int BFS(int Y, int X) {
    queue<pair<int, int> > Q;
    Visited[Y][X] = true;
    Q.push(make_pair(Y, X));
    int R = 0;

    while (!Q.empty()) {
        int NowY = Q.front().first;
        int NowX = Q.front().second;
        Q.pop();
        
        R++;

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < N) && !Visited[NextY][NextX] && (MAP[NextY][NextX] == 0)) {
                Visited[NextY][NextX] = true;
                Q.push(make_pair(NextY, NextX));
            }
        }
    };

    return R;
}

void settings() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if ((MAP[i][j] == 0) && !Visited[i][j]) {
                int R = BFS(i, j);
                if (R % K == 0) {
                    Answer += (R / K);
                }
                else {
                    Answer += ((R / K) + 1);
                }
            }
        }
    }
}

void find_Answer() {
    if (Answer >= 1) {
        if (M >= Answer) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if ((MAP[i][j] == 0) && !Visited[i][j]) {
                        cout << "IMPOSSIBLE\n";
                        return;
                    }
                }
            }
            cout << "POSSIBLE\n";
            cout << M - Answer << "\n";
        }
        else {
            cout << "IMPOSSIBLE\n";
        }
    }
    else {
        cout << "IMPOSSIBLE\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}