[BOJ] 7569 - 토마토 (3차원, BFS)

사용 언어: Python3

문제

백준 7569

풀이

import sys
from collections import deque
input = sys.stdin.readline # ✅ 대용량 입력에 대해 시간 단축

def countZero(board): # 3차원 리스트인 board에서 0의 개수를 카운트하는 함수
    cnt = 0
    for h in range(H):
        for i in range(N):
            for j in range(M):
                if board[h][i][j] == 0:
                    cnt += 1
    return cnt

dx, dy, dh = [0,-1,0,1,0,0], [1,0,-1,0,0,0], [0,0,0,0,1, -1] # ✅ 상/하/좌/우/위/아래 6가지 방향
def BFS():
    while q:
        x, y, h = q.popleft()
        for w in range(6):
            xx, yy, hh = x+dx[w], y+dy[w], h+dh[w]
            if xx<0 or xx>=N or yy<0 or yy>=M or hh<0 or hh>=H:
                continue
            if board[hh][xx][yy] == 0 and visited[hh][xx][yy] == 0:
                board[hh][xx][yy] = board[h][x][y] + 1 # ✅ 각 토마토마다 익는데 며칠이 걸리는지 체크하기 위해 1씩 누적
                q.append((xx, yy, hh))
                visited[hh][xx][yy] = 1

M, N, H = map(int, input().rstrip().split())
board = [[list(map(int, input().rstrip().split())) for _ in range(N)] for _ in range(H)] # ✅ 3차원 리스트 입력받기
visited = [[[0] * M for _ in range(N)] for _ in range(H)]
q = deque()

for h in range(H): # ✅ 3차원 리스트 순회: h -> i -> j
    for i in range(N):
        for j in range(M):
            if board[h][i][j] == 1:
                q.append((i, j, h))

BFS()

mx = -2147000000
for side in board:
    mx = max(mx, max(map(max, side)))
print([-1, mx - 1][countZero(board) == 0]) # ✅ (mx - 1) 해야한다 !!

• 시간초과를 주의해야 하는 문제이다!
• 상/하/좌/우/위/아래 총 6방향으로 돌아야 한다.
• 🌟 현재 값을 이전 값 + 1 으로 업데이트 하는 방법으로 BFS가 종료되면, 저장된 값들 중 최댓값이 곧 BFS의 “최소 탐색 횟수”가 된다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기