[python] 백준 7569번: 토마토(BFS)

# 7569 토마토
https://www.acmicpc.net/problem/7569

7569번: 토마토

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque

move = [(0,0,1), (0,0,-1), (1,0,0), (0,1,0), (-1,0,0), (0,-1,0)]
M, N, H = map(int, input().split())
graph = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)] # 3차원
queue = deque()


for i in range(H):
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 1:
                  queue.append((i,j,k))

while queue:
    i, j, k = queue.popleft()
    
    for di, dj, dk in move:
        ni = di + i
        nj = dj + j
        nk = dk + k

        if ni < 0 or ni >= H or nj < 0 or nj >= N or nk < 0 or nk >= M:
            continue
        if graph[ni][nj][nk] == -1:
            continue
        if not graph[ni][nj][nk]:
            graph[ni][nj][nk] = graph[i][j][k] + 1 # 시간체크
            queue.append((ni, nj, nk))
            
answer = 0
    for i in range(len(floor)):
        answer = max(max(floor[i]) - 1, answer)

for floor in graph:
    for row in floor:
        if 0 in row:
            answer = -1

print(answer)

📝 풀이

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

기존의 토마토 문제에서 위 아래의 상자가 추가됐다. 풀이의 로직은 비슷하고 탐색할 때 위 아래 탐색을 추가해줘야 한다.

🔓 정답 코드 뜯어보기

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

move = [(0,0,1), (0,0,-1), (1,0,0), (0,1,0), (-1,0,0), (0,-1,0)] # 1번
M, N, H = map(int, input().split())
graph = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)] # 2번
queue = deque()

for i in range(H): # 3번
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 1:
                  queue.append((i,j,k))

# 1번

상하좌우 + 윗상자 + 아랫상자를 탐색하기 위해 탐색범위를 설정해준다.

 

# 2번

3차원 배열을 생성하기 위해 높이 H만큼 반복문을 실행하고 N만큼의 리스트를 생성해준다.

 

# 3번

3차원 배열을 탐색하면서 익은 토마토(1)를 만나면 그 위치를queue에 담아준다.

while queue: 
    i, j, k = queue.popleft()
    
    for di, dj, dk in move: # 1번
        ni = di + i
        nj = dj + j
        nk = dk + k
		
        if ni < 0 or ni >= H or nj < 0 or nj >= N or nk < 0 or nk >= M: # 2번
            continue
        if graph[ni][nj][nk] == -1:
            continue
        if not graph[ni][nj][nk]: # 3번
            graph[ni][nj][nk] = graph[i][j][k] + 1 # 시간체크
            queue.append((ni, nj, nk))

# 1번

방향설정 값을 각각 di, dj, dk에 할당하고 현재 위치에 이동할 값을 ni, nj, nk에 저장시켜준다.

 

# 2번

탐색 범위가 범위를 넘어가게 된다면 continue해주고, 토마토가 들어있지 않은 칸이라면 continue해준다.

 

# 3번

탐색값이 0이라면 (익지않은 토마토) 그 위치에 이전 값에 1을 추가해준다. 1을 추가하는 이유는 안익은 토마토가 익는데 하루가 걸리기 때문에 익은 토마토를 기준으로 탐색할때 이전 값에 1을 추가해주는 방식으로 기록한다.

answer = 0
# [[[5, 4, 3, 4, 5], [4, 3, 2, 3, 4], [5, 4, 3, 4, 5]], [[4, 3, 2, 3, 4], [3, 2, 1, 2, 3], [4, 3, 2, 3, 4]]]
for floor in graph:
    for i in range(len(floor)):
        answer = max(max(floor[i]) - 1, answer) # 1번

for floor in graph: # 2번
    for row in floor:
        if 0 in row:
            answer = -1

print(answer)

# 1번

3차원 배열을 for문으로 벗겨주고 각각의 배열의 최댓값을 기록시켜준다. 시간 기록을 1부터 시작했기 때문에 최댓값에서 -1을 해줘야 정확한 값이 나오며, 각각의 answer을 비교해서 최댓값을 갱신시켜준다.

 

# 2번

만약 모든 토마토를 익힐 수 없다면 즉, 배열에 0이 존재한다면 answer의 값을 -1으로 저장시켜준다.