[백준] 7576. 토마토 python

🐳 링크

백준 7576번 토마토

🐕 문제

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

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

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

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

🐾 풀이 방법

• 토마토가 있다면, 그 위치를 큐에 넣어준다.
• 큐가 빌 때 까지 while문을 돌린다.
  큐의 사이즈만큼 for문을 돌린다.
  상하좌우로 이동해서 안익은 토마토가 있다면 익은 토마토로 바꾸어준다.
  익은 토마토로 바뀐 위치를 큐에 다시 넣어준다.
• while문이 끝나고 나왔을 때, 토마토에 안익은 토마토가 존재하지 않는다면 while 문을 돌린 횟수 즉, days를 리턴하고 아니면 -1을 리턴한다.

solution 코드

1. bfs이용, 정답코드

   import sys
   import copy
   from collections import deque
   sys.setrecursionlimit(10**9)
   sys.stdin = open("input.txt","rt")
   dx = [1,-1,0,0]
   dy = [0,0,1,-1]
   
   

def bfs(tomatoes):
days = -1
while farm: #익지않은 토마토가 존재하는 동안
days += 1
for _ in range(len(farm)):
x, y = farm.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<= nx < n and 0 <= ny < m and tomatoes[nx][ny] == 0:
                tomatoes[nx][ny] = tomatoes[x][y] + 1
                farm.append((nx,ny))
for tomato in tomatoes:
    if 0 in tomato:
        return -1
return days

m,n = map(int,sys.stdin.readline().split())
tomatoes = list()
for _ in range(n):
tomatoes.append(list(map(int,sys.stdin.readline().split())))

farm = deque()

for i in range(n):
for j in range(m):
if tomatoes[i][j] == 1:
farm.append((i,j)) #farm에 익은 토마토의 위치를 넣어준다.

print(bfs(tomatoes))

2. 테스트케이스만 맞고 시간초과나는 코드
```python3
import sys
import copy
sys.setrecursionlimit(10**9)
sys.stdin = open("input.txt","rt")
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def isNear(i,j):
    global after
    for _ in range(4):
        x = i + dx[_]
        y = j + dy[_]
        if 0 <= x < n and 0 <= y < m and tomatoes[x][y] == 1:
            after[i][j] = 1
            return

m,n = map(int,sys.stdin.readline().split())
tomatoes = list()
for _ in range(n):
    tomatoes.append(list(map(int,sys.stdin.readline().split())))


days = 0
after = copy.deepcopy(tomatoes)

while True:
    days += 1
    for i in range(n):
        for j in range(m):
            if tomatoes[i][j] == 0:
                isNear(i,j)

    if tomatoes == after:
        chk = False
        for k in range(n):
            if 0 in tomatoes[k]:
                chk = True
                break
        if chk: days = -1
        else:
            days -= 1
        break
    tomatoes = copy.deepcopy(after)

sys.stdout.write(str(days))