[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
Author And Source
이 문제에 관하여([Python] 7576 토마토), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yuchan/Python-7576-토마토저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)