[python] 백준 7576 번 : 토마토 (골드 5)

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

해당 문제는 탐색 문제 이다. 해당 문제를 풀때 고민했던 점은 날짜수를 세기 위해서는 날짜수를 세야 하므로 하루가 지날때 익는 토마토를 어떻게 분리하여 구하는지 였다. 그리하여 그 다음날 익을 토마토를 저장하는 stack 을 2개 만들어서 stack1에는 그 다음날 익을 토마토를 넣어주고 stack2 에는 다음날 익을 토마토가 무엇인지 찾아서 넣어주고 그날이 끝나면 초기화 해준다.

import sys
input = sys.stdin.readline

col_length, row_length = map(int,input().split())
box = list()
stack1 = stack2 = list()
for _ in range(row_length):
    box.append(list(map(int,input().split())))

for r in range(row_length):
    for c in range(col_length):
        if box[r][c] == 1:
            stack1.append((r,c))
count = 0
result = True
while stack1:
    stack2 = stack1[:]
    stack1.clear()
    while stack2:
        row , col = stack2.pop()

        if row + 1 < len(box) and box[row+1][col] == 0:
            stack1.append((row+1,col))
            box[row+1][col] = 1
        if row - 1 >= 0 and box[row-1][col] == 0:
            stack1.append((row-1,col))
            box[row-1][col] = 1
        if col+1 < len(box[0]) and box[row][col+1] == 0:
            stack1.append((row,col+1))
            box[row][col+1] = 1
        if col - 1 >= 0 and box[row][col-1] == 0:
            stack1.append((row,col-1))
            box[row][col-1] = 1  
    count += 1
    stack2.clear()
        
for r in range(row_length):
    for c in range(col_length):
        if box[r][c] == 0:
            result = False
if result:
    print(count-1)
else:
    print(-1)

마지막에 출력할때 count-1을 해주는 이유는 마지막으로 익은 토마토가 익을 토마토가 없지만 익을 토마토를 찾아서 반복문을 한번 더 돌기 때문이다.