알고리즘
[알고리즘] 백준 파이썬 27737 버섯 농장
chaewonni
2025. 1. 8. 23:58
📍 문제 탐색하기
이번 문제인 버섯 농장은 N×N 크기의 나무판에서, 버섯이 자랄 수 있는 칸(0)에 버섯 포자를 심어서 모든 버섯 가능 칸을 덮는 문제이다.
하지만 여기엔 두 가지 특별한 조건이 있다
- 한 포자는 심어진 칸을 포함해 최대 K개의 상하좌우로 연결된 칸에 버섯을 자라게 할 수 있음
- 한 칸에 여러 개의 포자를 심을 수 있음
- 만약 x개의 포자를 같은 칸에 겹쳐 심으면, 그 칸을 포함해 최대 x×K개의 연결된 칸에 버섯이 자라게 된다.
문제 이해가 제일 어려웠다. 좀 더 설명해보자면
- 단순히 모든 0 칸에 한 개씩 포자를 심는다면 당연히 버섯은 다 자라지만, 포자를 너무 많이 사용하게 된다.
- 더 적은 포자로 전부 덮으려면, 각 0 칸들이 어떻게 연결되어 있는지(상하좌우로 이어진 덩어리)를 구분하여, 한 포자로 얼마나 많은 칸을 덮을 수 있는지를 계산해야 한다.
- 또한 포자를 하나도 사용하지 않고 0칸이 없다면(즉, 전부 1이라서 버섯을 심을 곳이 없으면) 문제에서 요구하는 “포자를 하나 이상 사용” 조건을 만족시킬 수 없으므로, 이 역시 특별한 예외가 된다. -> 중요!!!!!!!!!!!
이 조건을 생각 못해서 틀렸다.
입력 범위
- 1≤N≤10: 나무판은 최대 100×100 크기
- 0≤M≤1,000,000: 버섯 포자 개수
- 1≤K≤10^8: 한 포자가 덮을 수 있는 최대 연결 칸 수
- 나무판의 각 칸은 0(버섯 가능), 1(버섯 불가)
가능한 시간복잡도
- 최대 N=100 ⇒ 나무판 최대 크기는 100×100=10,000
- 0(버섯 가능) 칸끼리 상하좌우로 연결된 구역(덩어리)을 BFS/DFS로 찾을 때, 전체 탐색 범위는 N×N에 비례하여 O(N^2)내에 충분히 처리 가능하다.
- 연결된 칸을 찾고, 각 덩어리마다 포자 수를 계산하는 과정도 문제없이 처리할 수 있다.
알고리즘 선택
연결된 구역을 탐색할 때 큐를 이용해 반복적으로 처리하므로 재귀 깊이 제한 문제를 피할 수 있을 것 같아 DFS가 아닌 BFS를 선택했다.
📍 코드 설계하기
- 입력 처리
- N,M,K를 입력받고, N줄에 걸쳐 나무판 상태를 입력받는다.
- 만약 0이 전혀 없다면, 즉시 IMPOSSIBLE을 출력하고 종료한다. (포자를 하나도 못 쓰므로 문제의 조건을 만족 못 함)
- 연결 구역 탐색
- BFS로 0이 이어진 칸들의 크기를 구한다.
- 덩어리 크기가 size라고 할 때, 해당 덩어리를 덮는 데 필요한 포자 수는 ⌈size/K⌉ (반올림)이다.
- 판단 후 결과 출력
- 전체 필요한 포자 수가 M보다 크면 IMPOSSIBLE.
- 그렇지 않으면 POSSIBLE과 남은 포자(M - 사용량)를 출력한다.
📍 시도 회차 및 수정 사항
1차 시도 (틀림) ❌
import sys
import math
from collections import deque
input = sys.stdin.readline
N, M, K = map(int, input().split())
farm = []
result = 0
for _ in range(N):
farm.append(list(map(int, input().split())))
# 상 하 좌 우
dx = [0, 0, -1 , 1]
dy = [-1, 1, 0, 0]
def bfs(r,c):
global result
global cnt
queue = deque([(r,c)])
farm[r][c] = 1
while queue:
r,c = queue.popleft()
for i in range(4):
nr = r + dx[i]
nc = c + dy[i]
if 0 <= nr < N and 0 <= nc < len(farm[0]):
if farm[nr][nc] == 0:
cnt += 1
queue.append((nr, nc))
farm[nr][nc] = 1
result += math.ceil(cnt / K)
for i in range(N):
for j in range(len(farm[0])):
if farm[i][j] == 0:
cnt = 1
bfs(i,j)
if result > M:
print('IMPOSSIBLE')
else:
print('POSSIBLE')
print(M-result)문제점: 0이 하나도 없는 경우 처리 부족
1차 시도에서는 0이 하나도 없는 상황(모든 칸이 1)일 때도 result = 0으로 계산되면서 결과가 POSSIBLE로 출력되는 문제가 있었다.
“포자를 하나 이상 사용해야 한다”는 조건을 충족하지 못해서 틀렸다..
2차 시도 (맞음) ✅
import sys
import math
from collections import deque
input = sys.stdin.readline
N, M, K = map(int, input().split())
farm = []
zero = False # 0칸이 존재하는지 확인!
result = 0
for _ in range(N):
row = list(map(int, input().split()))
farm.append(row)
if 0 in row:
zero = True
if not zero:
print('IMPOSSIBLE')
sys.exit(0)
# 상 하 좌 우
dx = [0, 0, -1 , 1]
dy = [-1, 1, 0, 0]
def bfs(r,c):
global result
global cnt
queue = deque([(r,c)])
farm[r][c] = 1
while queue:
r,c = queue.popleft()
for i in range(4):
nr = r + dx[i]
nc = c + dy[i]
if 0 <= nr < N and 0 <= nc < len(farm[0]):
if farm[nr][nc] == 0:
cnt += 1
queue.append((nr, nc))
farm[nr][nc] = 1
result += math.ceil(cnt / K)
for i in range(N):
for j in range(len(farm[0])):
if farm[i][j] == 0:
cnt = 1
bfs(i,j)
if result > M:
print('IMPOSSIBLE')
else:
print('POSSIBLE')
print(M-result)0이 하나도 없는 경우를 처리해주었다.
📍 느낀점
문제의 조건도 꼼꼼히 확인해야겠다..^^