백준 7576 토마토 Python 3

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

7576번: 토마토

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ7576.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque
imput = sys.stdin.readline
M, N = map(int, input().split())
box = list()
q = deque(list())
for i in range(N):
    box.append(list(map(int, input().split())))
    for j in range(M):
        if box[i][j] == 1: q.append([j, i, 0])
if not q: print(-1)
else:
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    while q:
        x, y, day = q.popleft()
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            if 0 <= nx < M and 0 <= ny < N and box[ny][nx] == 0:
                box[ny][nx] = 1
                q.append([nx, ny, day+1])
    for row in box:
        if 0 in row:
            print(-1)
            break
    else:
        print(day)

---

풀이 과정

풀이 시간 24분

import sys
from collections import deque

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

#토마토들이 담긴 박스
box = list()
q = deque(list())
for i in range(N):
    box.append(list(map(int, input().split())))
    for j in range(M):
    	#익은 토마토인 경우, 해당 토마토를 기준으로 인접한 토마토를 탐색하기 위해 (x, y) 위치와 시작일인 0을 큐에 담는다
        if box[i][j] == 1: q.append([j, i, 0])
        
#익은 토마토가 한 개도 없는 경우, -1을 출력한다
if not q: print(-1)

#익은 토마토가 있는 경우, BFS를 수행한다
else:
	#좌, 상, 우, 하
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    while q:
    	#현재 익은 토마토의 위치와 날짜
        x, y, day = q.popleft()
        
        #인접한 4 방향 탐색
        for ddx, ddy in zip(dx, dy):
            nx = x + ddx
            ny = y + ddy
            #해당 방향에 안 익은 토마토가 있는 경우,
            if 0 <= nx < M and 0 <= ny < N and box[ny][nx] == 0:
            	#하루가 지나 토마토가 익는다
                box[ny][nx] = 1
                q.append([nx, ny, day+1])
    
    #박스 안에 안 익은 토마토가 있는 경우, -1을 출력한다
    for row in box:
        if 0 in row:
            print(-1)
            break
    #모든 토마토가 익은 경우, day를 출력한다
    else:
        print(day)

#시간복잡도 = O(N*M), 공간복잡도 = O(N*M)