[백준|파이썬] 7569: 토마토 (골드5)

문제

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

7569번: 토마토

 

 

🐍파이썬

import sys
from collections import deque

def bfs():
    while queue:
    	#익은 토마토의 좌표를 기반으로 bfs 탐색
        x, y, z = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if nx >= m or ny >= n or nz >= h or nx < 0 or ny < 0 or nz < 0:
                continue
            if mato[nz][ny][nx] == 0:	#익지 않은 토마토에 방문
                mato[nz][ny][nx] = mato[z][y][x] + 1	#방문일수 저장
                queue.append((nx, ny, nz))	#다음 방문지로 해당 토마토의 좌표 저장

m, n, h = map(int, sys.stdin.readline().split())
mato = [[] for _ in range(h)]
for i in range(h):
    for _ in range(n):
        mato[i].append(list(map(int, sys.stdin.readline().split())))

#상하좌우/위아래 좌표
dx = [0, 0, -1, 1, 0, 0]
dy = [-1, 1, 0, 0, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
queue = deque()

for i in range(h):
    for j in range(n):
        for k in range(m):
        	#익은 토마토의 좌표를 큐에 모두 저장
            if mato[i][j][k] == 1:
                queue.append((k, j, i))
bfs()

#bfs 종료 후 토마토의 상태 확인
flag = False
answer = 0
for i in range(h):
    for j in range(n):
        for k in range(m):
            if mato[i][j][k] == 0:	#익지 않은 토마토 발견
                flag = True
                break
            #리스트 전체를 돌며 가장 큰 값을 업데이트하여 일수를 구하기
            answer = max(answer, mato[i][j][k])	
if flag:  #토마토가 모두 익지 못한 상태
    answer = -1
else:	#일수 출력/토마토가 처음부터 모두 익은 상태였다면 answer은 1이므로 0이 출력
    answer -= 1	#mato[i][j][k]에 저장된 일수는 1부터 시작하므로 0일부터 시작하도록 1을 빼준다
print(answer)

🐋소감

BFS의 기본 원리를 사용하는데 익숙해졌다 생각했지만 3차원 배열을 활용한 BFS 문제는 푸는 데는 시간이 많이 걸렸다. 값을 제대로 입력받는 데만 해도 많은 시간이 소요되었다😂

처음에 리스트 전체를 돌며 값이 1인 좌표를 먼저 모두 큐에 넣는 방식도 생소했고 마지막 삼중for문의 일수를 업데이트하는 코드는 도저히 혼자 생각해낼 수가 없어서 블로그들을 돌아다니며 도움을 받았다.

혼자 힘으로 풀어낼 수 있도록 여러번 복기해야겠다.

 

 

다른 풀이 방법

import sys
input=sys.stdin.readline
a,b,c=map(int,input().split())
q=[]
for i in range(b*c):q.append(list(map(int,input().split())))
dx=[0,0,1,-1]
dy=[1,-1,0,0]
du=[b,-b]

w=[]
e=[]

for i in range(b*c):
    for j in range(a):
        if q[i][j]==1:
            w.append(i)
            e.append(j)

def jake(w,e):
    ww=[]
    ee=[]
    for aa in range(len(w)):
        i=w[aa]
        j=e[aa]
        for ii in range(4):
            nx=i+dx[ii]
            ny=j+dy[ii]
            if 0<=nx<b*c and 0<=ny<a:
                if i//b==nx//b:
                    if q[nx][ny]==0:
                        ww.append(nx)
                        ee.append(ny)
                        q[nx][ny]=1
        for ll in range(2):
            nnx=i+du[ll]
            if 0<=nnx<b*c:
                if q[nnx][j]==0:
                    ww.append(nnx)
                    ee.append(j)
                    q[nnx][j]=1

    return ww,ee

count=0
while True:
    count+=1
    w,e=jake(w,e)
    if len(w)==0:
        break

for i in range(b*c):
    for j in range(a):
        if q[i][j]==0:
            count=0
            break

print(count-1)