[탐색/BFS] 백준 7569 토마토 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

7569번: 토마토

 

 

 

2. 문제 풀이

 익은 토마토 주위로 위아래, 동서남북으로 안 익은 토마토가 있으면 익습니다. 모든 토마토가 익으려면 총 며칠이 걸리는지 구해야 합니다.

 

2022.02.24 - [Algorithm] - [탐색/BFS] 백준 7576 토마토 - Python

[탐색/BFS] 백준 7576 토마토 - Python

 BFS탐색 문제입니다. 토마토 한 판(2차원)만 동서남북 방향으로 탐색하던 위 문제의 Upgrade 버전입니다. 이 문제는 3차원 리스트를 BFS탐색 해야합니다.

 

 

 

3. 코드

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

#입력
M, N, H = map(int, input().split()) #가로, 세로, 높이
tomato = []
queue = deque()
for z in range(H):
    floor = []
    for i in range(N):
        floor.append(list(map(int, input().split())))
        for j in range(M):
            # 잘 익은 토마토의 위치를 Queue에 입력
            if floor[i][j] == 1:
                queue.append((z, i, j))
    tomato.append(floor)

 우선 3차원 리스트로 토마토를 입력받습니다. 입력받으면서 잘 익은 토마토의 위치를 미리 queue에 넣어줍니다. 미리 queue에 넣어줘야, 번갈아가면 토마토가 BFS 탐색할 수 있습니다. (위 7576번 풀이링크 참조)

 

 

#BFS 탐색
day = 0 #토마토가 다 익는 데 걸리는 시간
direction = [[1, 0, 0], [-1, 0, 0], [0, 0, 1], [0, 0, -1], [0, 1, 0], [0, -1, 0]] #위아래, 동서남북 이동
while queue:
    z, x, y = queue.popleft() #큐에서 토마토 위치 꺼냄
    #토마토 주위 상하좌우 탐색
    for dz, dx, dy in direction:
        nz, nx, ny = z + dz, x + dx, y + dy
        #범위를 안 벗어나면서, 안 익은 토마토를 발견할 때
        if 0 <= nz < H and 0 <= nx < N and 0 <= ny < M and tomato[nz][nx][ny] == 0:
            queue.append((nz, nx, ny)) #익을 토마토
            tomato[nz][nx][ny] = tomato[z][x][y]+1

 동서남북으로 이동하던 방향벡터에서 위아래 이동만 추가해줍니다. 이후, Z축 방향도 고려해서 탐색합니다.

 

 

check = False #안 익은 토마토 있는지
for z in tomato:
    for i in z:
        for j in i:
            #안 익은 토마토 발견
            if j == 0:
                check = True
                break
        #안 익은 토마토가 있을 시 -1 출력 후 종료
        if check:
            break
        day = max(day, max(i))
    #안 익은 토마토가 있을 시 -1 출력 후 종료
    if check:
        print(-1)
        break

# 다 익었을 경우, 걸린 일수 출력
else:
    print(day-1) #맨 처음 익은 토마토 1은 필요 일수에서 제외

 3중 for문이라서 break를 3번이나 썼습니다.... goto문이 그립긴 하군요. 함수로 만들어서 return해주는 편이 더 깔끔하겠습니다.

 

 

day = 0
def isRipe():
    global day
    for z in tomato:
        for i in z:
            for j in i:
                #안 익은 토마토 발견
                if j == 0:
                    return False
            day = max(day, max(i))
    #안 익은 토마토가 없을 시, 다 익음
    return True

if isRipe():
    print(day-1)
else:
    print(-1)

 안 익은 토마토가 있을 시에는 -1를 출력하고, 다 익었으면 걸린 일수를 출력합니다.

 

 

<전체코드>

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

#입력
M, N, H = map(int, input().split()) #가로, 세로, 높이
tomato = []
queue = deque()
for z in range(H):
    floor = []
    for i in range(N):
        floor.append(list(map(int, input().split())))
        for j in range(M):
            # 잘 익은 토마토의 위치를 Queue에 입력
            if floor[i][j] == 1:
                queue.append((z, i, j))
    tomato.append(floor)

#BFS 탐색
day = 0 #토마토가 다 익는 데 걸리는 시간
direction = [[1, 0, 0], [-1, 0, 0], [0, 0, 1], [0, 0, -1], [0, 1, 0], [0, -1, 0]] #위아래, 상하좌우 이동
while queue:
    z, x, y = queue.popleft() #큐에서 토마토 위치 꺼냄
    #토마토 주위 상하좌우 탐색
    for dz, dx, dy in direction:
        nz, nx, ny = z + dz, x + dx, y + dy
        #범위를 안 벗어나면서, 안 익은 토마토를 발견할 때
        if 0 <= nz < H and 0 <= nx < N and 0 <= ny < M and tomato[nz][nx][ny] == 0:
            queue.append((nz, nx, ny)) #익을 토마토
            tomato[nz][nx][ny] = tomato[z][x][y]+1

day = 0
def isRipe():
    global day
    for z in tomato:
        for i in z:
            for j in i:
                #안 익은 토마토 발견
                if j == 0:
                    return False
            day = max(day, max(i))
    #안 익은 토마토가 없을 시, 다 익음
    return True

if isRipe():
    print(day-1)
else:
    print(-1)