[백준 27737] 버섯 농장 [Java]

문제

http://boj.ma/27737

27737번: 버섯 농장

 

---

풀이

문제 요약

M개 이하의 버섯 포자를 심어 모든 빈 공간에 버섯이 자라도록 하자.

아이디어

독립된 빈 공간을 탐색하며 최소한의 버섯 포자를 사용했을 때, 모든 영역에 버섯이 자라도록 할 수 있는지 확인해야 한다. 버섯 포자를 최소 1개 이상 사용해야하며, 모든 영역을 채우기 위해 필요한 버섯 포자의 수가 M보다 크다면 불가능하다.

    // Solve
		int m = M;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (board[i][j] == 0) {
					m -= (bfs(i, j) + (K - 1)) / K;
				}
			}
		}

		// Output
		if (m < 0 || m == M) {
			System.out.println("IMPOSSIBLE");
		} else {
			System.out.println("POSSIBLE");
			System.out.println(m);
		}

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/27737.java

problem-solving/baekjoon-online-judge/easy/27737.java at main · rogi-rogi/problem-solving