[백준]27737번: 버섯농장

▶ 문제 탐색하기

재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다. 

 

◇ 입력

1. 징검다리 개수 N (1~10,000 정수)
2. N개의 징검다리에 쓰여진 자연수 ---> arr =[]
3. 시작 a번째 징검다리, 도착 b번째 징검다리

 ◇ 원하는 출력 조건

1.  a번 징검다리에서 b번 징검다리로 최소 몇 번 점프해서 갈 수 있는지? 
2. 만약 갈 수 없다면 -1 출력N : 나무판 길이 (1≤N≤100)
   M : 버섯 포자의 수 (0≤M≤1,000,000)
   K : 버섯이 자라는 최대 칸수 (1≤K≤108)
3. 버섯 포자를 최소 개수로 심을 때 농사가 가능하지 판단하고, 가능하면 남은 버섯 포자 개수를 출력하는 문제이다.

가능한 시간복잡도 

 

알고리즘 선택

- BFS 알고리즘 사

▶ 코드 설계하기

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

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

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

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

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

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

만약 이 몫이

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

 

▶ 회차별 수정사항

▶ 정답 코드

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')

 

▶ 추가 풀이