[TIL] 백준 27737 - 버섯 농장 ( python )

📌 문제 탐색하기

N : 나무판의 행, 열

M : 버섯포자 개수

K : 한개의 버섯포자에서 최대로 버섯이 자랄 수 있는 개수

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

최소 개수로 버섯 포자를 심는 것이 핵심입니다.

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

가능한 시간복잡도

N의 최댓값은 100이므로 전체 나무판의 수는 100 * 100 = 10,000개입니다.

외부 이중 반복문과 BFS 모두 O(N^2) 시간복잡도를 가지므로, 최악의 경우에도 약 10,000번의 기본 연산을 수행합니다.

1초에 약 100,000,000번의 연산을 수행할 수 있으므로 시간 안에 탐색을 완료할 수 있습니다.

알고리즘 선택

시작 노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식인 BFS 알고리즘으로 접근해 보겠습니다.

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. 방문 체크를 위한 visited 배열을 초기화합니다.(False)
3. BFS 탐색을 구현합니다.
   1. 초기 시작 노드를 방문 체크한 후 queue에 넣습니다.
   2. count 변수를 1로 초기화합니다. 현재 포자로 커버한 칸의 수를 나타냅니다.
   3. 큐가 빌 때까지 다음을 반복합니다.
      1.  큐에서 좌표를 꺼내고, 상하좌우 네 방향에 대해 다음 조건을 검사합니다.
         • 좌표가 격자 범위 내에 있고,
         • 아직 방문하지 않았으며,
         • 해당 칸이 0(버섯이 자랄 수 있는 칸)이고,
         • count < K 인 경우 (포자가 커버할 수 있는 최대 칸에 아직 도달하지 않았을 때)
      2. 조건이 만족되면, 해당 칸을 방문 처리하고 count를 1 증가시키며 큐에 앞으로 방문해야 할 노드를 추가합니다.
4. 2중 for문을 사용해 모든 나무판자의 칸을 순회합니다.
5. 0인 칸에 대해 아직 방문하지 않았다면 BFS를 호출하고, 포자 사용을 의미하는 answer를 1 증가시킵니다.
6. 사용한 포자 수가 M 이하면 "POSSIBLE"과 남은 포자 수를, 아니면 "IMPOSSIBLE"을 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

1회 차

• 75% 정답률로 실패했습니다.
  
  • 'answer != 0' 조건 추가
    최소 한 개 이상의 포자를 반드시 사용해야 하므로,
    결과 검사를 수행하는 if문에 answer != 0 조건을 추가하여 answer가 0인 경우를 처리해야 합니다.
    

---

📌 정답 코드

import sys
input = sys.stdin.readline
from collections import deque

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

def bfs(y, x):
    global visited

    q = deque()
    q.append((y, x))
    visited[y][x] = True
    count = 1

    while q:
        y, x = q.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] 
            and matrix[ny][nx] == 0 and count < K:
                visited[ny][nx] = True
                count += 1
                q.append((ny, nx))


N, M, K = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
answer = 0

for y in range(N):
    for x in range(N):
        if matrix[y][x] == 0 and not visited[y][x]:
            bfs(y, x)
            answer +=1

if answer != 0 and answer <= M:
    print('POSSIBLE')
    print(M - answer)
else:
    print('IMPOSSIBLE')