[백준 2024/04/04] 7576번 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

1. 접근 방법

이번 문제는 dfs가 아닌 bfs로 접근해야하는 문제라고 생각이 들었다.

같은 level에 위치한 값에 대해서, 좌우상하 퍼져나가는 것을 같은 시간대에 진행해야하기 때문이다.

만약 dfs로 진행한다면, 한 익은 토마토에 대해서 전체 박스에 퍼져나간 후, 다음 익은 토마토에 대한 코드를 진행하기 때문이다.

따라서 bfs로 재귀적으로 코드를 구성하고 문제를 푸니 recursion error가 발생하였다.

무언가 잘못 구성한 것 같은데 잘 모르겠어서, queue로 바꾸어서 풀었다.

 

이는 앞 문제, 1012번 유기농 배추와 같은 레파토리였다.

queue를 이용함으로서 에러가 나지 않고 해결할 수 있었다.

 

 

queue를 이용하여 재귀적으로 구성하지 않고도 풀이가 가능하다.

익은 토마토들을 파악한 후 이를 queue에 넣어준 후 함수로 보내준다.

queue가 빌 때까지 while문을 돌린 후, 현재 queue값을 기준으로 pop을 진행한다.

만약 처음 익은 토마토가 2개였다면 for문은 2번 돌리게 될 것이다. 2번 돌리면서, 해당 익은 토마토를 기준으로 상하좌우를 확인하고, 

이중 리스트 기준 안에 있고 0이라면, 해당 값을 1로 바꾸어주었다.

 

이렇게 진행한 후 queue가 비게 된 다는 것은 더 이상 접근할 토마토가 없는 것이므로 days를 반환해준다.

 

2. 코드

from collections import deque


def bfs():
    days = -1
    while queue:
        days += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and tomato[nx][ny] == 0:
                    tomato[nx][ny] = 1
                    queue.append((nx, ny))
    return days


def check_zero():
    for x in range(m):
        for y in range(n):
            if tomato[x][y] == 0:
                return True

    return False


n, m = map(int, input().split())

tomato = []
for _ in range(m):
    line = list(map(int, input().split()))
    tomato.append(line)

queue = deque()
for x in range(m):
    for y in range(n):
        if tomato[x][y] == 1:
            queue.append((x, y))

answer = bfs()

if check_zero():
    print(-1)
else:
    print(answer)