7576-トマト(Python/Python)
11062 ワード
質問リンク:https://www.acmicpc.net/problem/7576
BFS問題
に答える
BFS問題
from collections import deque
import sys
input = sys.stdin.readline
m, n = map(int,input().split())
queue = deque()
matrix = []
# visit 그래프에는 각 칸의 토마토가 익는데 걸리는 시간을 표시
visit = [[-1]*m for _ in range(n)]
for i in range(n) :
new = list(map(int, input().split()))
matrix.append(new)
for j in range(m) :
# 익은 토마토가 있을 경우 queue에 추가해 bfs 탐색의 출발점으로 입력
if new[j] == 1 :
queue.append([i,j])
visit[i][j] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(queue) :
if len(queue) == 0 :
return -1
while queue :
y, x = queue.popleft()
for i in range(4) :
ny = y + dy[i]
nx = x + dx[i]
if nx < 0 or nx >= m or ny <0 or ny >= n :
continue
if matrix[ny][nx] == 0 and visit[ny][nx] == -1 :
queue.append([ny,nx])
visit[ny][nx] = visit[y][x] + 1
# 모든 칸을 돌면서 토마토가 있지만 접근하지 못한 칸이 있는지 체크
# 가장 오래 걸린 시간도 체크
days = 0
for i in range(n) :
for j in range(m) :
if matrix[i][j] == 0 and visit[i][j] == -1 :
return -1
if matrix[i][j] == 0 and visit[i][j] > -1 :
days = max(days,visit[i][j])
return days
print(bfs(queue))
Reference
この問題について(7576-トマト(Python/Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@jaenny/백준-7576-토마토-파이썬pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol