BAEKJOON #7576 토마토

이 문제의 저작권은 BAEKJOON에 있습니다.

 

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

문제는 위 링크에서 확인할 수 있습니다.

 

#토마토
#https://www.acmicpc.net/problem/7576
import sys
from collections import deque
M, N = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

#좌우상하
idx = [-1, 1, 0, 0]
idy = [0, 0, 1, -1]
get_one = deque()

first_cnt = 0
for i in range(N):
    for j in range(M):
        #토마토 요소가1인 지점에 있다.
        if arr[i][j] == 1:
            #1이 있는 좌표를 수집
            first_cnt += 1
            get_one.append((i, j))
cnt = 0
while get_one:
    gi, gj = get_one.popleft()
    value = arr[gi][gj]
    cnt += 1
    for i in range(4):
        get_y = gi + idy[i]
        get_x = gj + idx[i]     
        #arr의 범위를 벗어날 수 없다.
        if 0 <= get_y < N and 0 <= get_x < M:
            #토마토가 있는지 확인한다.
            if arr[get_y][get_x] == 0:
                arr[get_y][get_x] = value + 1 # 몇일째인지 일수 더하기
                get_one.append((get_y, get_x))
check = True
maxone = 0
for a in arr:
    if max(a) > maxone:
        maxone = max(a)
    if 0 in a:
        check = False
        break
if first_cnt == cnt:
    print(0)
elif check is True:
    print(maxone - 1)     
else:
    print(-1)

 

• 1. 익은 토마토(1)가 있는 좌표를 확인합니다. 토마토가 있다면 좌표를 배열에 삽입합니다.
• 2. 배열에 좌표값이 존재한다면 while문이 시작됩니다.
• 3. 이미 추가된 좌표값을 기준으로 상, 하, 좌, 우를 비교합니다.
• 4. 좌표값이 arr안에 존재하고 익지 않은 토마토(0) 일 경우에 배열에 삽입합니다. 
  • 4-2. 현재 좌표가 가지는 요소의 값 + 1 의 값을 익힐 토마토의 위치에 삽입합니다. 
  • [토마토를 익히지 않고 (1 로 바꾸지 않고) 익는 날짜를 삽입한다.]
• 5. while문을 모두 돌았다면 익지 않은 토마토가 있는지 검사합니다.
  • 5-1. 만약 처음 익은 토마토의 개수와 모든 작업 후 익은 토마토 개수가 같다면 0을 출력합니다.
  • 5-2. 그렇지 않고 익지 않은 토마토가 있다면 (arr 배열에서 가장 큰 값 - 1)을 출력합니다.
  • 5-3. 위의 경우가 아닐 경우 모든 토마토가 익을 수 없는 경우이므로 -1을 출력합니다.