meatsby.github.io

BOJ 7576 - 토마토

3 min read

풀이

역시나 BFS 문제이다. 하지만 이번엔 시작점이 여러개인 탐색을 해야하기 때문에 다른 방법을 요구했다.

먼저 입력으로 정보를 받은 뒤 익어있는 토마토의 좌표를 큐에 집어넣어둔다.

이후 BFS 를 실행하여 익어있는 토마토와 인접한 익지 않은 토마토들을 찾은 뒤 처음 익어있던 토마토는 1 로 저장되어 있으니 바로 인접한 토마토들을 +1 하여 저장해준다. 이 과정을 BFS 가 끝날 때 까지 반복한다.

이후 BFS 가 종료된 상태에서의 2차원 배열을 순회하면서 출력조건에 맞춰서,

익지않은 토마토가 있을 경우 -1 을,

이미 다 익어 있을 경우 0 을,

아니라면 가장 높은 숫자에서 -1 을 한 값을 출력해주면된다.

소스코드

# 토마토
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs():
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:  # 범위 내 이면서 익지 않았을 경우
                q.append([nx, ny])
                graph[nx][ny] = graph[x][y] + 1  # 방문 처리 겸 일수 계산
    return
 
 
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
q = deque()
 
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append([i, j])  # 이미 익어있는 토마토들을 큐에 삽입
 
bfs()  # BFS 실행
 
allRipe = True
ans = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            allRipe = False
            break
        ans = max(ans, graph[i][j])
 
if allRipe == False:
    print(-1)
elif ans == 1:
    print(0)
else:
    print(ans - 1)

References

Graph View