[Python] 7576 토마토

👉 7576 토마토

[정답 코드]

import sys
import copy
from collections import deque

def check_matrix_zero(matrix):
    zero = True
    for i in matrix:
        if 0 in i:
            zero = False
    return zero

def check_tomato_loc(matrix, tomato_loc, n, m):
    if matrix[n][m] == 0:
        matrix[n][m] = 1
        tomato_loc.append((n, m))

def bfs(matrix, tomato_loc):
    cnt = 0
    while tomato_loc:
        for loc in copy.deepcopy(tomato_loc):
            if loc[0] > 0:
                check_tomato_loc(matrix, tomato_loc, loc[0] - 1, loc[1])
            if loc[0] < n - 1:
                check_tomato_loc(matrix, tomato_loc, loc[0] + 1, loc[1])
            if loc[1] > 0:
                check_tomato_loc(matrix, tomato_loc, loc[0], loc[1] - 1)
            if loc[1] < m - 1:
                check_tomato_loc(matrix, tomato_loc ,loc[0], loc[1] + 1)
            tomato_loc.popleft()
        cnt += 1
    return cnt

m, n = map(int, sys.stdin.readline().split())
matrix = []
for i in range(n):
    matrix.append(list(map(int, sys.stdin.readline().split())))

tomato_loc = deque()
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            tomato_loc.append((i, j))


if check_matrix_zero(matrix): # 0 not in matrix
    print(0)
else:
    cnt = bfs(matrix, tomato_loc)
    if check_matrix_zero(matrix): # 0 not in matrix
        print(cnt - 1)
    else:
        print(-1)

[풀이]

• deque에 값이 1인 좌표(토마토가 익은 곳)를 모두 append 한 뒤, 하나씩 popleft()하며 bfs를 진행했다. 이 때 값이 0인 좌표(토마토가 익지 않은 곳)는 deque에 append해준다.

[오류 해결]

RuntimeError: deque mutated during iteration

deque으로 반복문을 돌릴 때 deque의 내용이나 사이즈가 변질될 때 나타나는 오류
copy or deepcopy를 통해 해결 가능
RuntimeError

[적용 자료구조 및 알고리즘]

• Graph
• DFS, BFS