백준 7576번: 토마토 [python]

난이도 : 백준 5
유형 : 그래프 탐색 (BFS)
다중 시작점 BFS (여러 개의 시작점)
https://www.acmicpc.net/problem/7576

문제 접근

가로 M 세로 N 크기의 박스 안에 토마토들이 들어가있다.
이 토마토들은 하루가 지나면 익는다. 그리고 이 토마토의 사방에 토마토들이 있다면 그 인접한 토마토들도 익는다.

전체 토마토들이 모두 익는데 걸리는 최소 시간을 구하는 문제.

토마토들이 익으면 1, 익지 않았으면 0.
그리고 시간이 흘러도 익지 않은 토마토가 있다면 -1을 출력한다.

1. M,N , box를 입력받는다.

2. 상하좌우를 탐색해야 하므로 방향벡터 dx,dy 리스트를 선언한다

3. BFS로 풀기위해 큐를 선언하고 익은 토마토의 좌표를 큐에 넣는다.

4. BFS함수를 선언한다. BFS는 큐의 요소가 존재한다면 계속 반복한다.
   4-1. 큐에서 익은 토마토의 좌표를 빼내서 상하좌우 네번 반복하여 탐색한다.
   4-2. 인접한 상하좌우의 위치가 박스에 범위에 들어가고 토마토가 익지 않았다면(0) 처음 이동하기전 좌표에 1을 더해준 숫자를 넣는다. 이때 1을 더해준 숫자는 하루가 지낫음을 의미한다.
   4-3. 그리고 그 인접한 좌표도 큐에 넣어준다.

5. BFS함수를 돌았음에도 box에 0이 있다면 -1을 print해준다.
   5-1. day 값중 가장 큰 day값을 찾는다.

6. day-1 을 해준값을 출력한다. (처음 날이 0이어야 하는데 1로 계산했으므로.)

해답 및 풀이

from collections import deque
import sys
input = sys.stdin.readline

# 1 . M,N , box를 입력받는다.
M, N = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(N)]

# 2. 상하좌우를 탐색해야 하므로 방향벡터 dx,dy 리스트를 선언한다
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 3. BFS로 풀기위해 큐를 선언하고 익은 토마토의 좌표를 큐에 넣는다.
queue = deque()

# 익은 토마토의 좌표를 큐에 넣기
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            queue.append((i, j))

# 4. BFS함수를 선언한다. BFS는 큐의 요소가 존재한다면 계속 반복한다.
while queue:

3 4-1. 큐에서 익은 토마토의 좌표를 빼내서 상하좌우 네번 반복하여 탐색한다.
    x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
# 4-2. 인접한 상하좌우의 위치가 박스에 범위에 들어가고 토마토가 익지 않았다면(0) 처음 이동하기전 좌표에 1을 더해준 숫자를 넣는다. 이때 1을 더해준 숫자는 하루가 지낫음을 의미한다.
        if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0:
            box[nx][ny] = box[x][y] + 1  # 익게 하면서 날짜 +
# 4-3. 그리고 그 인접한 좌표도 큐에 넣어준다.            
            queue.append((nx, ny))

# 결과 계산
day = 0
for row in box:
    if 0 in row:
# 5. BFS함수를 돌았음에도 box에 0이 있다면 -1을 print해준다.    
        print(-1)
        exit(0)
# 5-1. day 값중 가장 큰 day값을 찾는다.        
    day = max(day, max(row))

# 6. day-1 을 해준값을 출력한다. (처음 날이 0이어야 하는데 1로 계산했으므로.)
print(day - 1)