[BOJ7569 - Python] 토마토

문제

---

7569번: 토마토

 

N×M×H 크기의 상자에 토마토들이 보관된다. (1칸 1토마토)

(입력으로 주어지는 값) 1 : 익은 토마토 / 0 : 익지 않은 토마토 / -1 : 토마토가 들어있지 않음

 

 

보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

인접한 곳 : 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 (총 6 방향)

 

창고에 보관된 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산 구하는 것이 문제이다.

 

만약 저장될 때부터 모든 토마토가 익어있는 상태이면 0, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

풀이

---

BFS를 사용하는 되는 문제이지만

얕게 생각했다가 틀리고, 시간 초과 때문에 헤맨 문제이다,,,,

 

또한 모든 토마토가 익어있는 상태인지, 토마토가 모두 익지는 못하는 상황인지 등 문제에서 주어진 조건들을 잘 확인해보아야 한다.

 

우선 내가 틀렸던 이유는 아래의 반례에서 찾을 수 있었다.

10 1 1
1 0 0 0 0 0 0 0 0 1

정답 : 4

 

익은 토마토들은 하루 동안 익음을 동시에 전파한다는 것을 주의해야 한다.

 

---

이 '동시에'에 집중하여 BFS를 다음과 같이 진행할 수 있다.

 

1. 주어진 입력에서 익은 토마토들의 위치를 전부 큐에 삽입한다.

2. 큐의 끝에 '-1'을 삽입한다. (어디까지가 입력으로 주어진 익은 토마토들인지를 표시하기 위함)

 

3. 큐에 들어가 있는 값들에 대해서 탐색을 진행하고, 익은 토마토가 생겼다면 그 위치를 큐에 삽입한다.

 

4-1. 큐에서 pop 했을 때 '-1'을 만났을 경우 뒤에 값들이 더 있다면 (= 하루동안 익은 토마토들이 더 생겼다면)

        큐의 끝에 '-1'을 또다시 삽입한 후 탐색을 더 진행한다. (어디까지가 하루에 익은 토마토들인지를 표시하기 위함)

4-2. 뒤에 값들이 더 없다면, 더 이상 탐색을 할 곳이 없다는 뜻이므로 BFS를 종료한다.

 

def BFS():
    global q
    ans = 0

    q.append(-1)  # -1 : 하루동안 익은 토마토의 범위를 표시하기 위함
    while q:
        temp = q.popleft()

        if temp == -1:  # 전날 익은 토마토에 대하여 전부 탐색했을 때
            if len(q) != 0:  # 새로 익은 토마토가 있는 경우
                q.append(-1)
                ans += 1
            else:  # 새로 익은 토마토가 없는 경우
                break

        else:
            z, y, x = temp[0], temp[1], temp[2]
            for i in range(6):
                nz = z + dz[i]
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= nz < H and 0 <= ny < N and 0 <= nx < M and tomato[nz][ny][nx] == 0:
                    tomato[nz][ny][nx] = 1
                    q.append((nz, ny, nx))

    return ans

 

 

코드

---

import sys
from collections import deque

dz = (1, -1, 0, 0, 0, 0)
dy = (0, 0, -1, 0, 1, 0)
dx = (0, 0, 0, -1, 0, 1)


def BFS():
    global q
    ans = 0

    q.append(-1)  # -1 : 하루동안 익은 토마토의 범위를 표시하기 위함
    while q:
        temp = q.popleft()

        if temp == -1:  # 전날 익은 토마토에 대하여 전부 탐색했을 때
            if len(q) != 0:  # 새로 익은 토마토가 있는 경우
                q.append(-1)
                ans += 1
            else:  # 새로 익은 토마토가 없는 경우
                break

        else:
            z, y, x = temp[0], temp[1], temp[2]
            for i in range(6):
                nz = z + dz[i]
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= nz < H and 0 <= ny < N and 0 <= nx < M and tomato[nz][ny][nx] == 0:
                    tomato[nz][ny][nx] = 1
                    q.append((nz, ny, nx))

    return ans


M, N, H = map(int, sys.stdin.readline().split())  # M : 가로 / N : 세로 / H : 높이

result = 0  # 출력값 (저장될 때부터 모든 토마토 익음 : 0 / 토마토가 모두 익지는 못함 : -1 / 최소 일수)
status = False

tomato = []  # 1 : 익음 / 0 : 익지 않음 / -1 : 없음
q = deque()  # 익은 토마토의 위치 (h, n, m)

for h in range(H):  # 밑 상자 ~ 윗 상자
    tomato.append([])
    for n in range(N):
        line = list(map(int, sys.stdin.readline().split()))

        for m in range(M):
            if line[m] == 1:  # 익은 토마토 -> 큐에 삽입
                q.append((h, n, m))
            if line[m] == 0:
                status = True

        tomato[h].append(line)

# 익지 않은 토마토가 있는 경우
if status:
    result = BFS()  # 너비 우선 탐색

    for h in range(H):
        for n in range(N):
            for m in range(M):
                if tomato[h][n][m] == 0:  # 익지 못하는 토마토가 있는 경우
                    result = -1

print(result)