[Python](BFS) 백준 7576번 : 토마토

---

< 접근 방법 >

1. 창고 모양을 그대로 arr라는 이차원 배열에 입력한다.
2. 방문하지 않았던 곳만을 방문하기 위해서 이차원 배열인 visited 배열도 만들어준다.
3. tomato 리스트에 익은 토마토의 좌표(arr의 값이 1인 칸의 좌표)를 넣어주고, not_tomato는 토마토가 원래 들어있지 않은 칸(arr값이 -1인 칸)의 개수이다.
4. bfs 함수 내에서 check를 통해 총 익게 되는 토마토의 개수를 세줄 것이고, 
   date라는 변수를 이용해 토마토가 익는 데 걸린 날짜를 세줄 것이다.
5. q에 tomato 리스트에 있는 토마토들의 좌표를 모두 담아주고, 방문 처리도 해준다.
6. q를 돌면서, 익은 토마토에서 상하좌우로 아직 익지 않은 토마토가 있다면 익혀 나간다. (visited += 1)
7. date변수는 visited - 1의 값으로 갱신해 나간다.
   (-1을 해주는 이유 : 방문 처리를 위해 처음 토마토들의 visited값을 1로 설정해뒀기 때문에 다시 빼줘야 한다.)
8. 모든 토마토가 익는 경우(check값, 즉 익게 되는 토마토의 개수가 창고 칸 수(N*M) - 토마토가 없는 칸 수(not_tomato)이면), 모두 익는데 걸린 최소 날짜인 date를 return하고, 모두 익지 못했다면 -1을 return 한다.

---

from collections import deque
def bfs():
    q = deque()
    check = len(tomato)     # 익게 되는 토마토 개수
    date = 0    # 토마토가 익는 데 걸린 날짜

    for i, j in tomato:
        visited[i][j] = 1
        q.append((i, j))

    while q:
        ci, cj = q.popleft()
        date = max(date, visited[ci][cj]-1)     # 걸린 날짜 update
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):   # 상하좌우 탐색
            ni = ci + di
            nj = cj + dj
            # 범위 내, 미방문, arr칸이 0(익지 않은 토마토)인 경우
            if 0<=ni<N and 0<=nj<M and not visited[ni][nj] and not arr[ni][nj]:
                q.append((ni, nj))
                visited[ni][nj] = visited[ci][cj] + 1
                check += 1  # 토마토 익음

    if check == N*M - not_tomato:   # 모든 토마토가 익는 경우(창고 칸 - 토마토 들어있지 않은 칸 = check)
        return date     # 모두 익는데 걸린 최소 날짜 return
    else:
        return -1   # 모두 익지 못했다면 -1 return


M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
tomato = []     # 토마토가 있는 좌표를 담기 위한 list
visited = [[0]*M for _ in range(N)]
not_tomato = 0  # 토마토가 들어있지 않은 칸

# [1] 익은 토마토들은 tomato 리스트에 담기, 토마토가 없는 칸(-1) 수 세기
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            tomato.append((i, j))
        elif arr[i][j] == -1:
            not_tomato += 1

# [2] bfs를 통해 최소 걸린 날짜 및 불가능 경우 return
print(bfs())

 

이해가 안되는 부분이 있으면 질문 주세요. 감사합니다.