백준 토마토 [7576] 파이썬(Python) 코드 + 해설

백준 7576 토마토 문제

 

문제 설명

철수의 토마토 농장에서는 M x N 크기의 격자 모양 상자에 토마토를 보관한다. 토마토 중에는 익은 토마토(1)도 있고, 익지 않은 토마토(0)도 있으며, 토마토가 들어있지 않은 칸(-1)도 있다. 익은 토마토는 하루가 지나면 인접한 네 방향(상, 하, 좌, 우)에 있는 익지 않은 토마토를 익게 만든다. 이때, 상자에 있는 모든 토마토가 며칠이 지나면 다 익는지, 그 최소 일수를 구하는 프로그램을 작성한다. 단, 처음부터 모든 토마토가 익어있으면 0을 출력하고, 모두 익지 못하는 상황이면 -1을 출력해야 한다.

문제 해결 방법

이 문제는 BFS(너비 우선 탐색)를 이용해 해결할 수 있다. BFS는 그래프의 모든 인접 노드를 방문하며 탐색하는 방법으로, 여러 단계에 걸쳐 확산되는 문제를 해결하는 데 적합하다. 익은 토마토가 인접한 토마토를 익게 만드는 과정을 BFS로 구현하여, 며칠이 걸리는지 구할 수 있다.

백준 7576 토마토 문제 파이썬(Python) 정답 코드

from collections import deque

# 입력 받기
M, N = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(N)]

# 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 익은 토마토의 위치를 큐에 추가
queue = deque()
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            queue.append((i, j))

# BFS 수행
def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위를 벗어나지 않고 익지 않은 토마토(0)인 경우
            if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1  # 날짜 갱신
                queue.append((nx, ny))

# BFS 호출
bfs()

# 결과 계산
max_days = 0
for row in box:
    for value in row:
        if value == 0:
            print(-1)
            exit()
        max_days = max(max_days, value)

# 최소 일수 출력 (1일을 빼줘야 초기 시작일 제외)
print(max_days - 1)

백준 7576 토마토 문제 파이썬(Python) 정답 코드 해설

1. 입력 받기: M과 N을 입력받고, 각 행의 토마토 상태를 2차원 리스트 box에 저장한다.
2. BFS 준비: 익은 토마토의 초기 위치를 queue에 저장한다.
3. BFS 탐색:
   • 큐에서 토마토 위치를 하나씩 꺼내 인접한 네 방향을 검사한다.
   • 익지 않은 토마토(0)를 발견하면, 익은 토마토로 바꾸고(box[nx][ny] = box[x][y] + 1) 큐에 새로 추가한다.
4. 결과 계산:
   • 모든 칸을 검사하여, 익지 않은 토마토가 남아 있으면 -1을 출력하고 종료한다.
   • 최대 일수 max_days를 구해 출력하되, 시작일(1)을 제외하고 출력한다.

백준 7576 제출 결과

백준 7576 토마토 문제 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.