백준 알고리즘) 7576번 토마토 파이썬

7576번 토마토 문제

링크: 7576번: 토마토 (acmicpc.net)

7576번: 토마토

 

최소날짜를 보고 bfs로 탐색하면 되겠구나라고 생각했습니다.

문제를 어느정도 풀다보니 골드의 문제까지는 어느정도 어떤 알고리즘을 사용하여 풀어나갈지

감이 잡히더라구요.

 

이런 류의 문제는 풀어본 유형중에도 비슷한 것이 많았어서 쉽게 쉽게 코드를 써나가고 쉽게 풀어낸 것 같습니다.

코드는

 

import sys
from collections import deque
input=sys.stdin.readline
q=deque()
d=[-1,1,0,0]
answer=0
def bfs():
    while q:
        y,x=q.popleft()
        for i in range(4):
            dx=x+d[i]
            dy=y+d[3-i]
            if 0<=dx<M and 0<=dy<N and board[dy][dx]==0:
                q.append((dy,dx))
                board[dy][dx]=board[y][x]+1
 
    find()
    
def find():
    global answer
    for i in board:
        for j in i:
            if j==0:
                answer=0
                return
            else:
                answer=max(answer,j)
                
M,N=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(M):
        if board[i][j]==1:
            q.append((i,j))
bfs()
print(answer-1)