Coding - Algo/python
[백준] 7576번:토마토 (python 파이썬)
jainn
2021. 2. 10. 14:43
728x90
문제
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
풀이
일반 que로 풀었더니 계속 시간초과가 났다.
deque로 풀고 해결 ㅠㅠ 흑
소스코드
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
ans = 0
while que:
flag=0
for _ in range(len(que)):
y, x = que.popleft()
for i in range(4):
nowx, nowy = x+dx[i], y+dy[i]
if 0<=nowx<m and 0<=nowy<n and arr[nowy][nowx]==0:
arr[nowy][nowx] = 1
flag=1
que.append([nowy, nowx])
if flag==1:
ans+=1
return ans
m, n = map(int, input().split())
arr = []
que = deque()
for i in range(n):
tmp = list(map(int, input().split()))
for j in range(m):
if tmp[j]==1:
que.append([i, j])
arr.append(tmp)
ans=bfs()
for i in range(n):
for j in range(m):
if arr[i][j] == 0:
print(-1)
exit()
print(ans)
반응형