[백준 / BOJ] C++ 27737 버섯 농장

27737번: 버섯 농장

 

문제

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

27737번: 버섯 농장

 

 

풀이

버섯 포자를 심을 때마다 개수를 세어준다. DFS로 포자를 심은 부분으로부터 연결되어 심을 수 있는 모든 구간에 포자를 심는다. 포자를 심고 최대 퍼져나갈 수 있는 칸까지 간 다음엔 다시 1부터 시작하고 포자를 심는다. 가능한 모든 공간에 포자를 심은 후에 사용한 포자 수가 0개이거나 사용한 포자 수가 준비한 포자 수보다 많은 경우 버섯 농사가 불가능한 경우고 이외의 경우에는 가능한 경우다. 버섯 농사가 가능한 경우 사용하고 남은 포자 수를 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, k, cnt, ans = 0;
int graph[101][101], visited[101][101] = {0};
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};

void dfs(int x, int y) {
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx < 0 || ny < 0 || nx >= n || ny >= n)
      continue;
    if (!visited[nx][ny] && graph[nx][ny] == 0) {
      if (cnt == k) {
        ans++;
        visited[nx][ny] = 1;
        cnt = 1;
        dfs(nx, ny);
      } else {
        visited[nx][ny] = ++cnt;
        dfs(nx, ny);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> graph[i][j];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (!visited[i][j] && graph[i][j] == 0) {
        cnt = 1;
        ans++;
        visited[i][j] = 1;
        dfs(i, j);
      }
  if (ans > m) {
    cout << "IMPOSSIBLE";
  } else if (ans == 0) {
    cout << "IMPOSSIBLE";
  } else {
    cout << "POSSIBLE\n"
         << m - ans;
  }
  return 0;
}