백준 7576번: 토마토

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론
• 너비 우선 탐색 (BFS)
  
  

✔ 코드

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().split())

box = []

for i in range(N):
    tmp = list(map(int, sys.stdin.readline().split()))
    for t in tmp:
        box.append(t)

queue = deque([])
for i in range(N*M):
    if box[i] == 1:
        queue.append(i)

count = -1
while queue:
    n = len(queue)
    count += 1
    for _ in range(n):
        tmp = queue.popleft()

        if tmp % M > 0:
            if box[tmp-1] == 0:
                queue.append(tmp-1)
                box[tmp-1] = 1

        if (tmp+1) % M > 0:
            if box[tmp+1] == 0:
                queue.append(tmp+1)
                box[tmp+1] = 1

        if tmp >= M:
            if box[tmp-M] == 0:
                queue.append(tmp-M)
                box[tmp-M] = 1

        if tmp < M*(N-1):
            if box[tmp+M] == 0:
                queue.append(tmp+M)
                box[tmp+M] = 1

tf = 0
for i in range(N*M):
    if box[i] == 0:
        tf = 1
if tf:
    print(-1)
else:
    print(count)

• 바로 인접한 토마토부터 차례차례 익기 때문에 큐 (Queue)를 사용하는 너비 우선 탐색 (BFS)을 하였다. 이때, 연산의 최소화를 위해 덱 (Deque) 모듈을 사용하였다.
• 기본적인 BFS 문제와 다르게 그래프 (Graph)를 표현하기 위한 2차원 배열 사용을 생략한다. 그 이유는 바로 인접한 노드들과만 규칙성 있게 연결되어 있기 때문이다. (연산으로 충분히 대신할 수 있다.)
• 또한 각 노드들을 1로 바꿔줌으로써 이미 탐색했다는 것을 표현할 수 있기 때문에 visited와 같은 배열을 사용하지 않는다.
• 익은 (값이 1인) 토마토들의 위치만 계속해서 큐에 넣어준다. 이때, while문 안에 굳이 또 for문을 쓴 이유는 각 세대를 구분하여 최소 일수를 구하기 위해서이다.
• 익을 수 있을 만큼 익히고 while문을 빠져나왔을 때 아직 안익은 토마토가 남아있다면, -1을 출력하도록 하였다.

살짝 꼰 BFS 문제라 당황했다. 위의 내용 중 2, 3번째 아이디어를 떠올리기가 어려웠다.

✔ 관련 개념

• 그래프 (Graph) 이론과 너비 우선 탐색 (BFS)