백준_7576_토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

해결 방법

> 토마토 상자가 주어지면 이튿날에 익은 토마토의 상하좌우의 토마토들이 익게 되고 다음날 또한 익은 토마토들의 상하좌우의 토마토가 익게 된다.

> BFS를 이용하여 익은 토마토는 queue에 넣고 상하좌우의 토마토를 체크한다.(이미 익은 토마토이면 넘어가고 익지 않은 토마토이면 토마토를 익힌 후 queue에 넣는다.)

> python collections 모듈 deque를 이용한다.

 

코드

import collections

 

x, y = map(int, input().split())

 

tomato = [] #토마토 판

queue = collections.deque([]) #익은 토마토 선별 후 queue에 삽입

 

unriped = 0 #익지 않은 토마토의 개수

 

#input

for j in range(y):

    tomato.append(list(map(int,input().split())))

    for i in range(x):

        if tomato[j][i] == 1:   #queue input

            queue.append((i,j))

        elif tomato[j][i] == 0:

            unriped += 1

 

day = 0

 

while queue:

 

    dx = [0,0,1,-1]

    dy = [1,-1,0,0]

 

    t = queue.popleft()

 

    _x = t[0]

    _y = t[1]

 

    #up dowm left right

    for i in range(4):

        nx = _x + dx[i]

        ny = _y + dy[i]

 

        if nx >= x or nx < 0 or ny >= y or ny < 0: #index check

            continue

        

        if tomato[ny][nx] != 0:

            continue

 

        tomato[ny][nx] = tomato[_y][_x] + 1

        queue.append((nx,ny))

        day = max(tomato[ny][nx], day)

        unriped -= 1

 

if unriped == 0:

    print(day-1)

else:

    print(-1)