[백준] 7569번: 토마토 (파이썬)

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

저번 x,y축만 있던 토마토 문제에서 z축이 추가된 문제이다.

 

#시작할 때 익은 토마토 위치 queue에 담기
for i in range(h):
    for j in range(m):
        for k in range(n):
            if graph[i][j][k] == 1:
                queue.append((i,j,k))

count = 0
while queue:
    bfs()
    count += 1

우선 시작할 때 익은 토마토의 위치를 queue에 담는다.

이후 queue가 빌 때 까지 bfs를 반복한다.

 

bfs의 코드를 살펴보겠다.

 

def bfs():
    temp = deque([])
    while queue:
        z,y,x = queue.popleft()
        # 위아래 탐색
        if z < h-1:
            if graph[z+1][y][x] == 0:
                graph[z+1][y][x] = 1
                temp.append((z+1,y,x))
        if z > 0:
            if graph[z-1][y][x] == 0:
                graph[z-1][y][x] = 1
                temp.append((z-1,y,x))

        #4방향 탐색
        for i in range(4):
            current_x, current_y = x + dx[i] , y + dy[i]
            if 0 <= current_x < n and 0 <= current_y < m:
                if graph[z][current_y][current_x] == 0:
                    graph[z][current_y][current_x] = 1
                    temp.append((z,current_y,current_x))
    queue.extend(temp)

현재 토마토의 위,아래,동,서,남,북 6방향을 다 봐줘야 한다.

위를 볼 때는 마지막층 이하, 아래를 볼 때는 1층 이상인 경우만 봐줘야 한다.

 temp에 토마토의 좌표를 기록하는 이유는 토마토가 익는 날을 count 해줘야 하기 때문이다.

일단 queue를 다 비우고, bfs를 호출할 때마다 count에 1을 추가해서 토마토가 익는 날을 기록했다.

 

[전체 코드]

from collections import deque

n,m,h = map(int,input().split())
graph = [ [] for _ in range(h)]
queue = deque([])
for i in range(h):
    for _ in range(m):
        temp = list(map(int,input().split()))
        graph[i].append(temp)

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

def bfs():
    temp = deque([])
    while queue:
        z,y,x = queue.popleft()
        # 위아래 탐색
        if z < h-1:
            if graph[z+1][y][x] == 0:
                graph[z+1][y][x] = 1
                temp.append((z+1,y,x))
        if z > 0:
            if graph[z-1][y][x] == 0:
                graph[z-1][y][x] = 1
                temp.append((z-1,y,x))

        #4방향 탐색
        for i in range(4):
            current_x, current_y = x + dx[i] , y + dy[i]
            if 0 <= current_x < n and 0 <= current_y < m:
                if graph[z][current_y][current_x] == 0:
                    graph[z][current_y][current_x] = 1
                    temp.append((z,current_y,current_x))
    queue.extend(temp)


#시작할 때 익은 토마토 위치 queue에 담기
for i in range(h):
    for j in range(m):
        for k in range(n):
            if graph[i][j][k] == 1:
                queue.append((i,j,k))

count = 0
while queue:
    bfs()
    count += 1

def is_all_ripe():
    for i in range(h):
        for j in range(m):
            for k in range(n):
                if graph[i][j][k] == 0:
                    return False
    return True

if is_all_ripe():
    print(count -1)
else:
    print(-1)

이제 BFS에 자신감이 어느정도 생긴 것 같다!😊