백준 7576 토마토

해설

하루가 지나면 인접한 곳에 있는 토마토가 전부 익는 상황이다. 그리고 토마토는 여러 곳에 존재할 수 있다. 최단거리 계산하듯이 토마토가 몇일에 익는지 bfs를 통해 계산한 후 가장 큰 값을 출력해주면 되는 문제다.

다만 주의할 점은 토마토가 여러 곳에 존재할 수 있기 때문에 만약 bfs를 돌면서 지금 익는 것이 더 빠른 경우에는 그 값을 업데이트해줘야 한다!! <- 이 부분이 포인트라고 생각했다

그리고 방문 정보를 저장할 배열을 따로 넣어줄 필요는 없다. 어차피 그래프 내에서 0일때만 체크해주면 되므로.

시간초과

계속해서 시간초과가 나길래 Pypy3로도 돌려보고 그랬는데 시간초과가 난 코드는 다음과 같다.

from sys import stdin
from collections import deque

input = stdin.readline

M, N = map(int, input().split())  # M : col, N : row
graph = []
tomato = []
check_zero = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 1:
            tomato.append((i, j))
        elif tmp[j] == 0:
            check_zero = 1
    graph.append(tmp)

q = deque()


def bfs(r, c):
    q.append((r, c))
    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] > (graph[x][y] + 1) or graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))


# 토마토 익히기
for (r, c) in tomato:
    bfs(r, c)

# 모든 토마토가 익은 뒤
def checkTomato():
    maxDate = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                return -1
            else:
                maxDate = max(maxDate, graph[i][j])
    return maxDate - 1  # 며칠 뒤에 다 익는지라서 -1


# 처음부터 모두 익어있는 경우
if check_zero == 0:
    print(0)
else:
    print(checkTomato())

tomato 배열을 따로 갖고 있고 그 안에서 반복문을 돌면서 bfs를 돌렸더니 시간초과가 났다... 그래서 tomato 배열을 따로 두는 대신 바로 q에 넣어줬더니 해결됐다.

최종 정답 코드

from sys import stdin
from collections import deque

input = stdin.readline

M, N = map(int, input().split())  # M : col, N : row
graph = []

q = deque()

check_zero = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 1:
            q.append((i, j))
        elif tmp[j] == 0:
            check_zero = 1
    graph.append(tmp)




def bfs():
    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] > (graph[x][y] + 1) or graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))


# 토마토 익히기
bfs()

# 모든 토마토가 익은 뒤
def checkTomato():
    maxDate = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                return -1
            else:
                maxDate = max(maxDate, graph[i][j])
    return maxDate - 1  # 며칠 뒤에 다 익는지라서 -1


# 처음부터 모두 익어있는 경우
if check_zero == 0:
    print(0)
else:
    print(checkTomato())

눈물없이 볼수없는 시간초과의 현장... 어디에서 시간이 줄줄 새고 있는지 열심히 잡아본 문제였다.