[백준] 27737 - 버섯 농장 (C++)

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

농부 해강이는 N × N 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있고, 해강이는 M개의 버섯 포자를 버섯이 자랄 수 있는 칸에만 심을 수 있다. 각 버섯 포자는 심어진 칸을 포함해 최대 K개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결된 칸은 상하좌우로 적어도 한 변을 공유하는 칸들의 집합이다. 또한 한 칸에 버섯 포자를 여러 개 겹쳐서 심을 수 있으며, 만약 x개의 버섯 포자를 겹쳐 심으면 포자가 심어진 칸을 포함해 최대 x × K개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯이 자란다.

K = 4일 때 버섯이 자라는 모습

해강이는 버섯 포자를 심을 때 최소 개수로만 심으려고 한다. 이때, 버섯 포자를 하나라도 사용하고 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능하다고 정의한다. 해강이가 농사가 가능할지 판단하고, 농사가 가능하다면 남은 버섯 포자의 개수를 출력하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100
• 0 ≤ M ≤ 1,000,000
• 1 ≤ K ≤ 100,000,000
• 버섯이 자랄 수 있는 칸 = 0, 버섯이 자랄 수 없는 칸 = 1

 

버섯이 자랄 수 있고 방문한 적이 없는 칸마다 너비 우선 탐색을 돌려 필요한 버섯 포자의 수를 구하고 그 값에 따라 버섯 농사가 가능한지 판단해 출력을 다르게 해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, K, 나무판 정보 입력받기
2. 초기 M 값을 따로 저장해 두고 이중 반복문을 통해 버섯이 자랄 수 있고 방문한 적이 없는 좌표에서 너비 우선 탐색을 통해 연결된 모든 칸에 방문 체크하기
   1. 너비 우선 탐색을 하면서 연결된 모든 칸의 개수를 세고, 버섯이 자랄 수 있는 모든 칸에 버섯이 자라게 하려면 필요한 버섯 포자의 개수를 구해 빼면서 진행하기
3. 버섯 포자를 초과해서 사용했거나 버섯 포자를 하나도 사용하지 않은 경우 "IMPOSSIBLE" 출력하기 / 아니라면 "POSSIBLE"을 출력하고 남은 버섯 포자 개수 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~2회차

• 버섯 포자를 하나라도 사용해야 한다는 조건을 고려하지 않으면 75%에서 틀리게 된다. 따라서 버섯 포자를 쓰지 않은 경우를 알 수 있도록 초기 m 값과 버섯 포자를 심고 난 m 값이 같다면 "IMPOSSIBLE"을 출력하도록 수정했다.

 

---

정답 코드

#include <iostream>
#include <queue>
#define pii pair<int,int>
using namespace std;

int n,init_m,m,k,dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
bool board[100][100],visit[100][100];

void bfs(int a, int b) {
    queue<pii> q;
    q.push({a,b});
    visit[a][b] = true;
    int cnt = 1;
    while (!q.empty()) {
        auto [x,y] = q.front();
        q.pop();
        for (int i=0; i<4; i++) {
            int cx = x+dx[i], cy = y+dy[i];
            if (cx<0 || cx>=n || cy<0 || cy>=n || visit[cx][cy] || board[cx][cy]) continue;
            q.push({cx,cy});
            visit[cx][cy] = true;
            cnt++;
        }
    }
    m -= (cnt%k==0 ? cnt/k : cnt/k+1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> init_m >> k;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) cin >> board[i][j];

    m = init_m;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (!board[i][j] && !visit[i][j]) bfs(i,j);

    if (m<0 || m == init_m) cout << "IMPOSSIBLE";
    else cout << "POSSIBLE" << '\n' << m;
}