백준 7576번 <토마토>

백준 알고리즘 7576번

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

7576번: 토마토

---

7576번

안 익은 토마토는 익은 토마토 옆에서 하루가 지나면 익는다. 토마토 보관 상자의 상태가 주어졌을 때, 모든 토마토가 익기까지 걸리는 최소 시간을 구하여라.

 

입력으로 상자의 크기를 나타내는 M(가로) , N(세로) 가 들어온다. 그리고 다음 N개의 줄에 상자의 각 세로 줄의 상태가 들어온다.

 

출력으로는 모든 토마토가 익기까지 최소 시간을 출력하면 된다.

처음부터 모든 토마토가 익어있을 경우에는 0을 출력하고 모든 토마토가 익을 수 없다면 -1을 출력한다.

---

문제 해결

이 문제는 BFS와 DFS 개념을 응용해서 풀면 된다.

 

n*m 배열의 graph를 만들어서 토마토 보관 상자의 상태를 모두 저장해두었다. 각 칸을 방문했는지를 나타내는 visit 배열을 또 만들기에는 메모리 크기가 너무 클 것 같아서 그냥 graph 배열을 사용하기로 했다.

또한 익은 토마토의 수와 전체 토마토의 수를 세서 만약 두 개가 같다면 0을 출력하였다.

 

익은 토마토를 저장하는 tomato 리스트를 사용하였다.

tomato 리스트에 있는 각 토마토들의 상하좌우를 확인하여 안 익은 토마토가 있다면 익게 만들었다. 그리고 새로운 익은 토마토를 저장하는 리스트를 만들었고 이 리스트에 대해서 tomato 리스트에 한 일을 반복해주었다.

새로운 익은 토마토 리스트의 길이가 0이거나 익은 토마토의 수와 전체 토마토의 수가 같다면 반복을 그만하면 된다.

---

코드

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

graph = [[] for _ in range (n)]
tomato = []
tomatoN = 0
sweet = 0
for i in range(n):
    graph[i] = list(map(int, input().split()))
    for j in range(m):
        if graph[i][j] == 1:
            tomato.append((i, j))
            graph[i][j] = -1
            tomatoN += 1
            sweet += 1
        elif graph[i][j] == 0:
            tomatoN += 1

if sweet == tomatoN:
    print(0)
    sys.exit()

iL = [-1, 0, 1, 0]
jL = [0, -1, 0, 1]

result = 0
while len(tomato) > 0:
    if sweet == tomatoN:
        break
    result += 1
    temp = []
    for i, j in tomato:
        for k in range(4):
            temp_i = i + iL[k]
            temp_j = j + jL[k]
            if temp_i < 0 or temp_j < 0 or temp_i >= n or temp_j >= m:
                continue
            if graph[temp_i][temp_j] == 0:
                temp.append((temp_i, temp_j))
                graph[temp_i][temp_j] = -1
                sweet += 1

    tomato = temp
if tomatoN != sweet:
    print(-1)
else:
    print(result)

---

결과

---