[Python/백준] 7576. 토마토

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

DFS/BFS

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

---

풀이

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

# 격자 상태의 상자들과 토마토 정보 주어졌을 때,
# 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램 작성.

# 입력 : 첫 줄에는 상자의 크기 N x M 정수 -> 둘 곱하면 100만 크기
# 둘째 줄부터 : 하나의 상자에 저장된 토마토들의 정보
# 1: 익은 토마토, 0: 아직 안 익은 토마토, -1: 토마토가 없는 칸(벽)
# 1이 0을 전염시키면서 1로 만듦.

M, N = map(int, input().split())
# 4 x 6 크기
# 0 0 0 0 0 0
# 0 0 0 0 0 0
# 0 0 0 0 0 0
# 0 0 0 0 0 1

# 이거 시간 재야 하니까 bfs로 풀어야겠는데?
# 거기에 델타 탐색으로, 1인 지점들 저장해놓고, 거기서부터 퍼져나가자.

# 우린 시간까지 같이 넣을 거임.

# 아래 반복문 list comprehension으로 개선하기!!
box = []
for _ in range(N):
    box.append(list(map(int, input().split())))
queue = deque((i, j, 0) for i in range(N) for j in range(M) if box[i][j] == 1)

# 상하좌우 델타값 정의
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# bfs
while(queue):
    x, y, t = queue.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0:
            box[nx][ny] = 1
            queue.append((nx, ny, t + 1))

for line in box:
    if line.count(0) != 0:
        print(-1)
        exit(0)

print(t)

---

250218 재풀이

from collections import deque
import sys

input = sys.stdin.readline

m, n = map(int, input().split())

# 모두 못 익으면 -1 출력
# 이미 모두 익어있으면 0 출력
# 아니면 모두 익을 최소 날짜 출력
# 1은 익은 토마토, 0은 안익은 토마토, -1은 벽
# 1이 0을 1로 만들며 퍼져나감
# 1이 여러개일 수 있음 -> queue에 다 넣고 bfs 돌리자!

tomato = [list(map(int, input().split())) for _ in range(n)]

# queue = deque()
# for i in range(n):
#     for j in range(m):
#         if tomato[i][j] == 1:
#             queue.append((i, j, 0))

queue = deque(((i, j, 0) for i in range(n) for j in range(m) if tomato[i][j] == 1))

# 2. 상하좌우 델타값 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

t = 0
# 2. queue가 빌 때까지,
while queue:
    # 3. pop하며 현재 정점에서 action 실행
    x, y, t = queue.popleft()
    # 4. 인접한 모든 정점들에 대해,
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 5. 방문x 인접한 정점으로 이동
        if 0 <= nx < n and 0 <= ny < m and tomato[nx][ny] == 0:
            tomato[nx][ny] = 1
            queue.append((nx, ny, t + 1))

# for line in tomato:
#     if line.count(0) >= 1:
#         print(-1)
#         break
# for 루프가 정상적으로 끝났을 때만 else가 실행되는 for-else 구문
# else:
#     # 토마토가 모두 익어있으면 그냥 바로 t = 0 출력됨
#     print(t)

# 정답 확인: 아래와 같이 구현하면 더 간결
# for line in tomato:
#     if 0 in line:
#         t = -1
#         break
#

def is_there_any_unripe_tomato():
    for line in tomato:
        if 0 in line:
            global t
            t = -1
            return

is_there_any_unripe_tomato()
print(t)