[파이썬/Python] 백준 27737번: 버섯 농장

숨·2024년 9월 11일

코테

알고리즘 문제 풀이

목록 보기

71/105

📌 문제 : 백준 27737번

📌 문제 탐색하기

N : 나무판 길이 $(1 ≤ N ≤ 100)$
M : 버섯 포자의 수 $(0 ≤ M ≤ 1,000,000)$
K : 버섯이 자라는 최대 칸수 $(1 ≤ K ≤ 10^8)$

버섯 포자를 최소 개수로 심을 때 농사가 가능하지 판단하고, 가능하면 남은 버섯 포자 개수를 출력하는 문제이다.

문제 풀이

⭐️ 버섯 포자 심는 조건

나무판의 0, 1이라고 적힌 곳 중 버섯이 자랄 수 있는 0의 칸에만 포자를 심을 수 있다.

한 칸에 버섯 포자 여러 개 겹쳐서 심을 수 있다.

x개의 버섯 포자 겹치면 최대 x * K개 연결된 칸 중 0이 적힌 칸에 버섯 자란다.

위의 조건으로 버섯 포자를 심을 때 최소 개수만 이용해야 한다.

하나의 버섯 포자는 상하좌우로 연결된 칸 중 최대 K개의 칸에 버섯을 자라게 할 수 있다.

🚨 농사 가능하다고 판단하는 기준은 버섯 포자 하나라도 사용
→ 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 이다.

전체 나무판을 탐색하면서 버섯이 자랄 수 있는 칸을 먼저 찾는다.
→ 버섯이 자랄 수 있는 칸만 탐색하니 이미 방문한 곳은 버섯이 자랄 수 없는 곳으로 표시를 변경해서 방문 처리해주면 되겠다!

해당 위치에서 BFS를 통해 상하좌우를 확인해서 연결된 영역을 찾는다!
→ 몇 개의 영역이 연결되었는지 계산해서 K로 나눠 포자 하나가 연결된 곳에 버섯을 자라게 할 수 있는 영역을 계산한다.

이 때, K로 나눈 몫이 바로 필요한 포자의 최소 개수가 될 것이다❗️

만약 이 몫이

M 이하라면? 몫을 M에서 빼 남은 포자 개수를 출력한다.
M 초과라면? 농사 불가능 → IMPOSSIBLE을 출력한다.

가능한 시간복잡도

전체 나무판 BFS 탐색 → $O(N^2)$

최종 시간복잡도
$O(N^2)$ 으로 최악의 경우 $O(10^4)$ 로 2초 내에 연산할 수 있을 것이다.

알고리즘 선택

전체 나무판에서 버섯이 자랄 수 있는 곳 찾아 BFS 수행하기

📌 코드 설계하기

BFS 함수 구현
필요한 입력 받기
이동 방향 정의
BFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

계속 75%에서 틀렸습니다가 나왔다.
확인해보니 버섯 포자를 반드시 사용해야 하는 조건이 있는데 이를 고려하지 않고 구현해서 발생한 문제였다.
따라서 포자 사용 여부를 체크하는 변수를 추가해서 이 변수가 False면 농사 불가능으로 출력하도록 구현해 해결했다.

📌 정답 코드

import sys, math
from collections import deque

input = sys.stdin.readline


def bfs(x, y):
    queue = deque([(x, y)])
    # 방문 처리
    boards[x][y] = 1
    # 연결된 영역 변수 정의
    areas = 1

    while queue:
        x, y = queue.popleft()
        # 상하좌우 확인
        for i in range(4):
            nx, ny = x + directions[i][0], y + directions[i][1]
            # 영역 내 버섯 자랄 수 있는 칸 있는지 확인
            if 0 <= nx < N and 0 <= ny < N and boards[nx][ny] == 0:
                # 방문 처리
                boards[nx][ny] = 1
                queue.append((nx, ny))
                # 영역 개수 카운트
                areas += 1
                # 최소 하나로
    return areas


# N, M, K 입력
N, M, K = map(int, input().split())

# 나무판 상태 입력
boards = [list(map(int, input().split())) for _ in range(N)]

# 상하좌우 이동 방향 정의
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# 전체 필요 포자 개수 변수 정의
total_nums = 0

# 최소 하나의 포자 사용했는지 여부 나타내는 변수 정의
use_seed = False

# 전체 탐색해 버섯 자랄 수 있는 칸 찾기
for i in range(N):
    for j in range(N):
        if boards[i][j] == 0:
            # BFS 수행
            areas = bfs(i, j)
            # 남은 포자 개수 얻기
            nums = math.ceil(areas / K)
            # 누적합 계산
            total_nums += nums
            # 포자 사용함 기록
            use_seed = True

# 결과 출력
if not use_seed:
    print('IMPOSSIBLE')
elif total_nums <= M:
    print('POSSIBLE')
    print(M - total_nums)
else:
    print('IMPOSSIBLE')