[BOJ] 7576, 7569: 토마토 BFS 풀이 (Python)

BOJ 7576번 토마토 (2차원)

문제

7576번: 토마토

7576번: 토마토

2차원 토마토 상자

풀이

최소 일수를 구해야하므로 BFS를 이용합니다.

익은 토마토의 위치를 모두 큐에 넣고, 인접위치(왼쪽, 오른쪽, 앞, 뒤)의 토마토를 확인하며 일수를 계산합니다.

마지막으로 익지 않은 토마토가 있는지 확인해줍니다.

from collections import deque

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

# 익은 토마토를 큐에 넣음
queue = deque()
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            queue.append((i, j, 0))

# 방향 지시자
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while queue:
    x, y, days = queue.popleft()
    
    # 인접위치 토마토 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        ndays = days + 1

        # 박스 영역 안인지 확인
        if 0 <= nx < n and 0 <= ny < m:
            # 안익은 토마토일 경우 익힘 처리 후 큐에 삽입
            if box[nx][ny] == 0:
                box[nx][ny] = 1
                queue.append((nx, ny, ndays))

# 익지 않은 토마토가 있을 경우 결과값 -1로 변경
for i in range(n):
    if box[i].count(0):
        days = -1
        break

print(days)

BOJ 7569번 토마토 (3차원)

문제

7569번: 토마토

7569번: 토마토

3차원 토마토 상자

 

풀이

2차원 토마토 문제와 동일하고, 인접위치는 왼쪽, 오른쪽, 앞, 뒤에서 위, 아래까지 확인해줍니다.

input()으로 입력받을 경우 시간 초과가 발생하므로 sys.stdin.readline()으로 입력받습니다.

import sys
from collections import deque
input = sys.stdin.readline
m, n, h = map(int, input().split())
box = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]

# 익은 토마토를 큐에 넣음
queue = deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if box[i][j][k] == 1:
                queue.append((i, j, k, 0))

# 방향지시자
df = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]

while queue:
    f, x, y, days = queue.popleft()

    # 인접위치 토마토 확인
    for i in range(6):
        nf = f + df[i]
        nx = x + dx[i]
        ny = y + dy[i]
        ndays = days + 1

        # 박스 영역 안인지 확인
        if 0 <= nx < n and 0 <= ny < m and 0 <= nf < h:
            # 안익은 토마토일 경우 익힘 처리 후 큐에 삽입
            if box[nf][nx][ny] == 0:
                box[nf][nx][ny] = 1
                queue.append((nf, nx, ny, ndays))

# 익지 않은 토마토가 있을 경우 결과값 -1로 변경
for i in range(h):
    for j in range(n):
        if box[i][j].count(0) > 0:
            days = -1
            break

print(days)