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

분노의 토마토...🍅

접근방법이 틀려서 알고리즘을 몇번씩 수정했다

 

🌼 문제 링크

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

7569번: 토마토

• 티어: 골드 V
• 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

❗ TRIAL 1.

코드

import sys
input = sys.stdin.readline

from collections import deque

M, N, H = map(int, input().split())

#fill tomatos (-1: no tomato, 0: raw tomato, 1: grown tomato)
tmt = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
for h in range(H):
    for n in range(N):
        tmt[h][n] = list(map(int, input().split()))

#BFS
adjs = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]
def BFS(v):
    visited = [[[False for _ in range(M)] for _ in range(N)] for _ in range(H)]
    queue = deque([(v, 0)])
    visited[v[0]][v[1]][v[2]] = True
    while queue:
        v, cnt = queue.popleft()
        for d in adjs:
            new_v = [v[i]+d[i] for i in range(3)]
            if 0<=new_v[0]<H and 0<=new_v[1]<N and 0<=new_v[2]<M:
                if tmt[new_v[0]][new_v[1]][new_v[2]] == 1:
                    return cnt+1
                elif not visited[new_v[0]][new_v[1]][new_v[2]] and tmt[new_v[0]][new_v[1]][new_v[2]] == 0:
                    visited[new_v[0]][new_v[1]][new_v[2]] = True
                    queue.append([new_v, cnt+1])
    return -1

def solution():
    maxcount = 0
    for h in range(H):
        for n in range(N):
            for m in range(M):
                if tmt[h][n][m] == 0:
                    cnt = BFS([h, n, m])
                    if cnt == -1:
                        return -1
                    if cnt > maxcount:
                        maxcount = cnt
    return maxcount

print(solution())

 

코드 설명

 

- 익은 토마토에서 한 스텝씩 익혀가는게 아니라,

- 모든 안익은 토마토에 대해 익은 토마토까지의 최단거리를 구하는 방식으로 품

 

틀린 원인

 

시간초과. 그냥 문제에서 주어진 대로 익은 토마토에서 한 스텝씩 나아가는 게 더 빠르다.

 

 

❗ TRIAL 2.

코드

import sys
input = sys.stdin.readline

from collections import deque

M, N, H = map(int, input().split())

#fill tomatos (-1: no tomato, 0: raw tomato, 1: grown tomato)
tmt = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
for h in range(H):
    for n in range(N):
        tmt[h][n] = list(map(int, input().split()))

#list of grown tomatos
growns = []
num_target = 0
for h in range(H):
    for n in range(N):
        for m in range(M):
            if tmt[h][n][m] == 1:
                growns.append((h, n, m))
            elif tmt[h][n][m] == 0:
                num_target += 1

dhs = [1, -1, 0, 0, 0, 0]
dns = [0, 0, 1, -1, 0, 0]
dms = [0, 0, 0, 0, 1, -1]

cnt = 0
while num_target > 0:
    new_target = num_target
    growns_tmp = []
    for vh, vn, vm in growns:
        for dh, dn, dm in zip(dhs, dns, dms):
            newh, newn, newm = vh+dh, vn+dn, vm+dm
            if 0<=newh<H and 0<=newn<N and 0<=newm<M:
                if tmt[newh][newn][newm] == 0:
                    tmt[newh][newn][newm] = 1
                    new_target -= 1
                    growns_tmp.append((newh, newn, newm))
    if new_target == num_target:
        cnt = -1
        break
    growns.extend(growns_tmp)
    num_target = new_target
    cnt += 1

print(cnt)

 

수정한 부분

 

- 익은 토마토의 목록을 처음에 저장하고,

- 매 step마다 인접한 익지 않은 토마토들을 익힌다.

- 처음에 익지 않은 토마토의 갯수를 count하고,

- 매 step이 끝날 때 익지 않은 토마토의 갯수가 줄지 않았으면 진행을 멈추고 -1을 반환, (더이상 진행할 수 없음)

- 익지 않은 토마토가 없으면 총 step 수를 return한다.

 

틀린 원인

 

시간초과. 매 step마다, 한번 검사한 익은 토마토는 다음번에 검사하지 않아도 됨 (이미 인접 토마토는 다 익었으니까)

 

💡 Solution

코드

import sys
input = sys.stdin.readline

from collections import deque

M, N, H = map(int, input().split())

#fill tomatos (-1: no tomato, 0: raw tomato, 1: grown tomato)
tmt = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
for h in range(H):
    for n in range(N):
        tmt[h][n] = list(map(int, input().split()))

growns = deque([])
num_target = 0
for h in range(H):
    for n in range(N):
        for m in range(M):
            if tmt[h][n][m] == 1:
                growns.append((h, n, m))
            elif tmt[h][n][m] == 0:
                num_target += 1

dhs = [1, -1, 0, 0, 0, 0]
dns = [0, 0, 1, -1, 0, 0]
dms = [0, 0, 0, 0, 1, -1]

cnt = 0
while num_target > 0:
    new_target = num_target
    new_growns = deque([])
    while growns:
        vh, vn, vm = growns.popleft()
        for dh, dn, dm in zip(dhs, dns, dms):
            newh, newn, newm = vh+dh, vn+dn, vm+dm
            if 0<=newh<H and 0<=newn<N and 0<=newm<M:
                if tmt[newh][newn][newm] == 0:
                    tmt[newh][newn][newm] = 1
                    new_target -= 1
                    new_growns.append((newh, newn, newm))
    if new_target == num_target:
        cnt = -1
        break
    num_target = new_target
    growns = new_growns
    cnt += 1

print(cnt)

 

코드 설명

• 익은 토마토의 목록을 처음에 저장하고 (growns),
• 매 step마다 익은 토마토와 인접한 익지 않은 토마토들을 익힌다. 이 때 새롭게 익은 토마토들의 목록을 저장한다 (new_gronws).
• 처음에 익지 않은 토마토의 갯수를 count하고 (num_target),
• 매 step이 끝날 때 익지 않은 토마토의 갯수가 줄지 않았으면 (if new_target == num_target) 진행을 멈추고 -1을 반환, (더이상 진행할 수 없음)
• 익지 않은 토마토가 없으면 총 step 수를 return한다.
• 다음 step에서는 새롭게 익은 토마토들의 목록을 이용해 동일하게 진행한다.

•