[백준7569] / 토마토 - BFS

 

백준7569

 

 

푼 날짜 : 2024.10.12

푼 문제 : [7569] / 토마토

사용한 언어 : python

알고리즘 : BFS

 

 

접근 방식 :

dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

 

위 아래 왼쪽 오른쪽 앞 뒤 이렇게 6방향을 처리해줘야 했으므로 위와 같이 구성했다.

사실 그렇게 어렵지는 않은 문제라 나머지는 코드의 주석으로 확인하면 좋을 것 같다 !

 

 

 

코드 :

import sys
from collections import deque

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

graph_ = [[] for _ in range(H)]
for i in range(H):
    for _ in range(N):
        lst = list(map(int, sys.stdin.readline().split()))
        graph_[i].append(lst)

visited = [[[-1 for _ in range(M)] for _ in range(N)] for _ in range(H)]

# 위 아래 왼쪽 오른쪽 앞 뒤 방향
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

flag = False # 토마토가 다 익었는지, 하나라도 안 익은게 있는지 체크하기 위함
queue = deque([])

# 토마토 익히기
def BFS():
    global queue

    while queue:
        now = queue.popleft()

        for i in range(6):
            nz, ny, nx = now[0]+dz[i], now[1]+dy[i], now[2]+dx[i]

            if 0<=nz<H and 0<=ny<N and 0<=nx<M:
                if visited[nz][ny][nx] == -1 and graph_[nz][ny][nx] == 0:
                    visited[nz][ny][nx] = visited[now[0]][now[1]][now[2]] + 1
                    queue.append((nz, ny, nx))

# 토마토 초기 위치 체크, 토마토 익은 개수 체크, 박스위치 체크
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))
                visited[i][j][k] = 0
            # 안익은 토마토가 있다면 flag를 True로 만들어 BFS돌리기 위함
            elif graph_[i][j][k] == 0: 
                flag = True
            # 토마토가 없는 칸은 그냥 101로 처리, 값의 범위가 100이하기 때문!
            else: 
                visited[i][j][k] = 101

if flag: # 토마토가 안익은게 있다면
    BFS()

    ans = -1
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if visited[i][j][k] == -1: # 안익은게 있다면 
                    print(-1)
                    exit()
                elif visited[i][j][k] != 101: # 방문한 위치이며 토마토가 없는 위치가 아닐 때
                    ans = max(ans, visited[i][j][k])
    print(ans)
    
else: # 토마토가 이미 다 익은 상태라면
    print(0)

 

 

평범한 BFS 문제가 위, 아래, 왼쪽, 오른쪽 만 체크한다면 이 문제는 앞, 뒤까지 체크한다는 점이 달랐다.

하지만 그것만 처리해준다면 쉬운 문제!