[백준 - Python] 7576. 토마토 (DFS/BFS)

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

7576번: 토마토

 

코드

from collections import deque

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

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

time = 0
queue = deque([])
def bfs(queue):
    global time
    tmp = len(queue)
    while queue:
        a, b = queue.popleft()
        tmp -= 1
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if box[nx][ny] == -1 or box[nx][ny] == 1:
                continue
            # 0으로 안익은 토마토를 만난 경우
            queue.append((nx, ny))
            box[nx][ny] = 1
        if tmp == 0:
            tmp = len(queue)
            if queue:
                time += 1

for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            queue.append((i, j))
# 시작 점만 넣어 주면 bfs 에서 카운팅
bfs(queue)

for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            print(-1)
            exit()
print(time)

 

시작할 때, 익은 토마토가 1개 이상일 수도 있다는 점에서 약간 까다로운 문제였다.

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 함으로,

BFS로 접근해야겠다는 생각을 했다.

 

토마토가 여러 개인 경우에 시간이 지남에 따라 인접 토마토들이 동시에 익어감으로

이를 처리해주는 것이 관건이었던 것 같다.

 

이코테 bfs 코드를 더 문제에 맞게 응용해서 해결하지 못했던 점이 아쉽다.

우선 주어진 값에서 익은 토마토의 좌표를 큐에 전부 넣어주고,

현재 큐에서 꺼내온 토마토와 인접한 토마토들이 존재할 때,

즉, queue가 비어있지 않은 경우에

시간 변수인 time을 +1 해주었다.

 

방금 처리한 토마토들의 인접 토마토들의 수만큼,

그 인접 토마토들을 또 익게 하기 때문에,

이번에 익은 토마토들을 popleft 해줄 때  tmp 변수로 카운팅해 주면서 처리했다.

 

토마토가 모두 익지 못하는 상황은

상자 전체를 돌면서 0이 존재하는 경우로 확인하여

-1을 출력해주었다.