백준 알고리즘 - 토마토 (7576) [Python]

 

 

 문제

 

www.acmicpc.net/problem/7576

7576번: 토마토

 

 

 

 

 

 

 문제 상황

 

- 토마토가 다 익는데 걸리는 최소 시간을 출력하고, 불가능하다면 -1을 출력한다.

 

 

 

 

 

 

 

 해결 전략

 

- 우선 0의 개수를 계산하여 전부 익었는지 확인하는데 사용한다. 그리고 같은 시간에 익는 토마토의 위치들을 새로운 큐에 넣어 작업을 반복한다.

 

 

 

 

 

 

 

 코드

 

from sys import stdin
from collections import deque
input = stdin.readline
M, N = map(int, input().split())
farm = [ list(map(int, input().split())) for _ in range(N) ]
visited = [[-1 for i in range(M)] for j in range(N)]
cnt = 0 # 0의 개수
sec = 0 # 익는데 걸리는 시간
riping = deque()
temp = [] # 같은 시간안에 처리되어야할 목록
for i in range(N): # 0의 개수 구하기
    for j in range(M):
        if farm[i][j] == 0 : 
            cnt += 1
            visited[i][j] = 0
        if farm[i][j] == 1 : temp.append((i,j))
riping.append(temp)
def bfs(x,y):
    global cnt
    dx, dy = [-1,1,0,0], [0,0,1,-1]
    temp = []
    for i in range(4):
        xx,yy = x+dx[i], y+dy[i]
        if 0<=xx<N and 0<=yy<M:
            if visited[xx][yy] == 0 and farm[xx][yy] == 0:
                visited[xx][yy] = 1
                farm[xx][yy] = 1
                temp.append((xx,yy))
                cnt -= 1
    return temp    
while riping and cnt != 0:
    check = riping.popleft()
    sec += 1
    temp = []
    for i in range(len(check)):
        x, y = check[i]
        temp.extend(bfs(x,y))
    if len(temp) !=0 : riping.append(temp)
print(sec if cnt == 0 else -1)

 

 

 

 

 

 

 

 

 해설

 

- 한번에 작동되는 부분이 여러개이므로 이를 동시에 처리하기 위해 temp 리스트를 만들어서 같은 시간에 동작하는 리스트를 선언하였다. 이후 cnt가 0이 아닌 조건, 즉 익어야할 토마토의 남은 개수가 존재할 때 사방을 탐색하며 작업을 반복한다.

 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 재귀가 직관적이지만 아직까지 논리를 생각하기는 반복문이 더 쉽다.