(BFS) 7576번 토마토

from collections import deque

m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
# 좌표를 넣을 것이기 때문에 [] 형태로 넣는다.
queue = deque([])
# 방향 리스트.
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
# 정답이 담길 변수
res = 0

# queue에 처음 위치 좌표를 넣는다.
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])

# bfs 함수. 한번 들어가면 다 돌고 나오니까 재귀 할 필요 없음
def bfs():
    while queue:
        # 처음 토마토 좌표 x, y에 꺼내고
        x, y = queue.popleft()
        # 처음 토마토 사분면의 익힐 토마토들을 찾아본다.
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            # 해당 좌표가 좌표 크기를 넘어가면 안되고, 그 좌표에 토마토가 익지 않은채로 있어야 함(0).
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                # 익히고 1을 더해주면서 횟수를 세어주기
                # 여기서 나온 제일 큰 값이 정답이 될 것임
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

bfs()
for i in matrix:
    for j in i:
        # 다 찾아봤는데 토마토를 익히지 못했다면 -1 출력
        # 지점마다 사이드를 확인해가면서 -1로 둘러 쌓여진 부분이 있으면 -1를 출력하려 했다.
        # 하지만 어차피 -1로 둘러 쌓여져 있으면 지점을 다 돌아도 0으로 남아 있기 때문에
        # 마지막에 0이 있냐 없냐만 체크해주면 되는 것은 좋은 아이디어이다.
        if j == 0:
            print(-1)
            exit(0)
    # 다 익혔다면 최댓값이 정답
    res = max(res, max(i))
# 처음 시작을 1로 표현했으니 1을 빼준다.
print(res - 1)

알고리즘 한문제당 1시간을 넘기지 않으려고 하다보니 일단 다른사람의 코드를 가져왔다.

처음에 DFS로 문제를 해결하려 했다가 잘 풀리지 않았다. 생각을 해보니 토마토 문제는 각 지점마다 사이드를 확인하면서 진행해야 하므로 DFS보다는 BFS로 푸는 것이 맞아보였다.

혼자서 다시 풀어봤을 때, 조건이

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

일 경우 이해가 안되어서, 각자 독립적으로 돌면서 최소 값을 저장해놓는 방식으로 구현했다.

import sys
from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split())

graph = []
for c in range(C):
    graph.append(list(map(int, input().strip().split())))  # 값을 입력 받는다.

queue = deque()
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def bfs(c, r):
    queue.append([c, r])

    while queue:
        c, r = queue.popleft()
        visited[c][r] = True

        for i in range(4):
            nc = c + dy[i]
            nr = r + dx[i]

            if 0 <= nc < C and 0 <= nr < R and graph[nc][nr] != -1 and visited[nc][nr] == False:
                queue.append([nc, nr])
                if graph[nc][nr] == 0:
                    graph[nc][nr] = graph[c][r] + 1

                else:
                    graph[nc][nr] = min(graph[c][r] + 1, graph[nc][nr])


for c in range(C):
    for r in range(R):
        if graph[c][r] == 1:
            visited = [[False for _ in range(R)] for i in range(C)]
            bfs(c, r)

answer = 0

for j in graph:

    for i in j:
        if i == 0:
            print(-1)
            exit(0)

        answer = max(answer, i)

if answer == 1:
    print(-1)

else:
    print(answer-1)

다만 메모리 초과가 발생했다. 그래서 정답 코드를 자세히 분석을 해보니 처음 que에 1의 좌표가 전부 들어간다. 그리고 큐는 선입 선출이므로 1이 여러개 있을 경우 서로 반복해서 돌아간다. 즉,

1 -1 0 0 0 0
1 -1 0 0 0 1
1 0 0 0 -1 1
0 0 0 0 -1 1

처럼

[0, 0], [3, 5] 가 반복으로 돌아가게 되어서 max 값이 9가 나오지 않는다. 서로 돌아가면서 최단 경로 값을 넣기때문에 그렇다. (0일 때만 실행을 하기 때문에!!)