PS/Python
[Python] 백준 #7576 토마토 - bfs
yoo.o
2020. 8. 17. 03:22
반응형
문제
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토�
www.acmicpc.net
풀이
#2178 미로탐색(https://yuuj.tistory.com/85)과 유사한 문제
import sys
from collections import deque
M, N = map(int, sys.stdin.readline().split(" "))
box = []
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for _ in range(N):
box.append(list(map(int, sys.stdin.readline().split(" "))))
queue = deque()
# 초기 토마토 위치 넣기
for i in range(N):
for j in range(M):
if box[i][j] == 1:
queue.append([i, j])
while queue:
i, j = queue.popleft()
for k in range(4):
ndr = i + dr[k]
ndc = j + dc[k]
if 0 <= ndr < N and 0 <= ndc < M and box[ndr][ndc] == 0:
queue.append([ndr, ndc])
box[ndr][ndc] = box[i][j] + 1
max = -1
flag = 0
for i in range(N):
for j in range(M):
if box[i][j] > max:
max = box[i][j]
if box[i][j] == 0:
max = 0
flag = 1
break
if flag == 1:
break
print(max-1)
반응형