[백준] 7576번 토마토 파이썬 정답 코드

7576번: 토마토

---

1. 문제 내용

 

 

2. 접근 방식

• 토마토가 익는 날짜를 파악하기 위해 graph[x][y] 값을 누적하자

초기 익은 토마토(i, j)는 1이다. 다음 날인 첫째날, 해당 토마토의 상하좌우에 있는 토마토는 (i, j) + 1 = 1 + 1 = 2가 된다. 이런 식으로 이전 날짜에 하루를 더하는 방식으로 0을 채워나가다 보면, 최대 날짜 값에서 -1한 값이 모든 토마토가 익을 때까지 필요한 최소 일수이다.

 

• 토마토가 모두 익을 수 없을 때는 너비 우선 탐색이 끝난 후에도 graph에 0이 존재한다.

어차피 graph 내 최대 값을 찾아내기 위해서는 graph를 탐색해야 한다. 이때 graph 내 0이 존재하는지 확인하자.

 

3. 정답 코드

from collections import deque


def get_initial_1_positions():
    data = deque([])  # 처음 1의 위치
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                data.append([i, j])
    return data


def get_answer():
    max_in_each_row = []
    for g in graph:
        if 0 in g:
            return -1

        max_in_each_row.append(max(g))

    return max(max_in_each_row) - 1


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

visited = [[0] * m for _ in range(n)]
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

points = get_initial_1_positions()

while points:
    x, y = points.popleft()

    for d in directions:
        dx = x + d[0]
        dy = y + d[1]

        if dx >= n or dx < 0 or dy >= m or dy < 0:
            continue

        if not graph[dx][dy]:
            graph[dx][dy] = graph[x][y] + 1
            points.append([dx, dy])

print(get_answer())

 

전체적으로 제출된 파이썬 정답은 메모리 사용이 크고 시간도 오래 걸렸지만, 1,500ms 이하의 시간이 걸리는 분들도 많았다. 시간을 줄일 수 있는 방법이 무엇일지 고민해 보아야겠다.