[백준] 7576. 토마토 Python

문제 링크 : 7576 토마토

7576번: 토마토

 

풀이 코드 : GIthub
 

문제

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

풀이

BFS문제이다. 

매일 토마토가 익어가는 칸을 BFS로 찾아가는것이 포인트이다.

 

 

코드

import sys 
from collections import deque

m, n = map(int, sys.stdin.readline().split(' '))

maps = []
for _ in range(n):
    maps.append(list(map(int, sys.stdin.readline().split(' '))))

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


queue = deque()
next_tomato_location = []
days = 0

for i in range(n):
    for j in range(m):
        if maps[i][j] == 1:
            queue.append((i, j))


while queue:
    while queue:
        y, x = queue.popleft()
        # for 문으로 현재 위치에서 상하좌우 다 찔러봄
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 현재위치에서 상하좌우 좌표가 갈수 있는지 확인
            if 0 <= nx < m and 0 <= ny < n and maps[ny][nx] == 0:
                maps[ny][nx] = 1
                next_tomato_location.append((ny, nx))
    queue = deque(next_tomato_location)
    next_tomato_location = []
    if queue:
        days += 1

flag = True
for i in range(n):
    for j in range(m):
        if maps[i][j] == 0:
            print(-1)
            flag = False
            break
    if not flag:
        break
if flag:
    print(days)

 

• Input을 받고 토마토의 위치가 담긴 Map을 만든다.
• 그 뒤 맨 처음 토마토가 있는 위치를 queue에 넣는다.
• 그 뒤 2중 while문을 돌며 BFS로 방문하는데
  • 하루가 지난 후 근처 토마토를 익게하는것을 구현하기 위함이다.  
  • 첫 번째 while은 모든 방문할수 있는 모든 토마토를 방문했는지 확인하기 위함이다.
  • 두 번째 while은 오늘 방문할 수 있는 모든 토마토를 모두 방문할때까지 반복하기 위함이다.
• 방문할 수 있는 모든 토마토를 방문하면 2중 while을 빠져나오게 된다.
• 그 후 방문하지 못한 토마토가 있는지 확인하고 (있다면 -1 출력)
• 며칠이 걸렸는지 출력한다.