코드

from collections import deque
m, n = map(int, input().split())

graph = []

# 1 : 익은 토마토, 0 : 안 익은 토마토, -1 : 토마토 없음
for _ in range(n):
    graph.append(list(map(int, input().split())))
    
# BFS
def solution():
    # 소요된 일수를 담을 변수
    day = 0
    
    q = deque()

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    
    # 토마토가 있는 곳의 좌표만
    # 큐에 넣어준다
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                q.append((i, j))

    while q:
        day += 1
        
        # 이 for문이 중요!!!
        # 모든 상자의 좌표에 대해서 반복을 돌리는 것이 아니라
        # 토마토가 있던 상자에 대해서만 반복을 돌려야
        # 정확한 일수가 계산된다
        for _ in range(len(q)):
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue

                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))
        
    # BFS가 끝났는데도 박스에 0이 있다면
    # 모든 토마토가 익을 수 없는 경우이므로
    # -1 반환
    for box in graph:
        if 0 in box:
            return -1
        
    # 첫날도 +1 했으므로 -1 해줘야 맞는 정답
    return day-1    

print(solution())

문제 해설

미로찾기와 유사한 BFS 문제이다.

전체를 다 탐색한 후, 그 중 가장 큰 값을 고르는 방식으로 문제를 도출해도 되지만, 뭔가 일수를 직접 세어가면서 답을 구하고 싶어 해당 방식으로 문제를 푸는 방향으로 답을 적었다.

 while q:
        day += 1
        
        # 이 for문이 중요!!!
        # 모든 상자의 좌표에 대해서 반복을 돌리는 것이 아니라
        # 토마토가 있던 상자에 대해서만 반복을 돌려야
        # 정확한 일수가 계산된다
        for _ in range(len(q)):
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

위의 코드에서 큐의 길이 만큼 반복을 추가해서 돌려줬는데, 이렇게 하지 않으면 전체 탐색 횟수만큼 day 변수가 증가하여 원하는 답을 구할 수가 없다. 따라서 큐의 길이 만큼 반복을 설정해줘 익은 토마토가 존재하는 박스의 좌표값에 맞춰 실행하면 그 개수에 알맞게 day 값을 구할 수 있다.

댓글남기기

참고