백준 7576번 토마토

문제 풀이

• 상자에 담긴 토마토를 graph로 나타내고, 맨 처음 graph에서 1인 값을 queue에 담고, BFS를 이용한 탐색을 시작합니다.
• 특별히 visited 변수를 사용할 필요는 없고, 기존의 토마토의 상태를 나타내는 graph에 탐색이 진행됨에 따라 현재 노드의 값에서 +1을 한 값을 넣습니다.
• 결과값은 graph의 원소들 중 최대값을 출력하면 됩니다.

코드 풀이

시간 초과 코드

• 생각을 정제하지 않고 의식의 흐름대로 작성한 코드입니다.
• 시간 초과가 발생하여, 생각을 정리하고, 좀 더 효율적인 방법을 생각해보았습니다.

import sys
from collections import deque
input = sys.stdin.readline

M, N = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]


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 not graph[nx][ny] and not visited[nx][ny]:
                    graph[nx][ny] = 1


result = -1
while True:
    status = False
    q = deque()
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1 and not visited[i][j]:
                q.append([i, j])
                visited[i][j] = 1
                status = True

    bfs()

    if not status:
        break

    result += 1

for i in range(N):
    for j in range(M):
        if not graph[i][j]:
            print(-1)
            exit()

print(result)

시간 초과 해결

• 탐색할 때, 그래프에다가 현재 위치에서의 값에서 +1을 해준 값을 넣고, 결과값은 그래프의 값 중 최대값을 출력하면 됩니다.

• 유의할 점: 마지막에 2차원 리스트인 graph의 최대값을 구할 때, max(max(graph)-1로 했을 시 답이 틀렸다고 나오고, 아래와 같이 할 시 정답으로 처리됩니다.
• 번거롭지만, 한 번에 이중으로 max를 적어주면 안되고, 위에 for문을 돌면서 max값을 갱신하면서 구해주어야 합니다.

import sys
from collections import deque
input = sys.stdin.readline

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


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 not graph[nx][ny]:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append([nx, ny])


q = deque()
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            q.append([i, j])

bfs()

result = 0
for i in range(N):
    for j in range(M):
        if not graph[i][j]:
            print(-1)
            exit()
    result = max(result, max(graph[i]))

# max(max(graph)) - 1로 하면 답이 틀림.
print(result - 1)