토마토 (백준 7659 -파이썬)

bfs 개념을 어느정도 익힌듯해서 답을 안 찾아보고 끝까지 풀어보고 싶었다. 결국 혼자 풀어냈지만 꽤 오래 걸렸다. 3차원 문제는 처음인데 재밌넹

풀이

필요 요소
1. 데이터 담을 3차원 배열
2. 날이 지날 때마다 익은 갯수를 세어주는 변수
3. 익은 토마토 주변을 탐색하기 위해 익은 토마토 좌표를 저장할 큐
4. 동서남북위아래 방향 데이터 (선택)

로직 순서
1. 데이터들을 3차원에 받으면서
2. 값이 1이면 큐에 담고 count_one 변수를 올려준다.
3. 값이 -1이면 count_minus 변수를 올려준다.
4. 데이터 개수에서 비어있는 토마토 수(-1의 개수)를 뺀 수를 ans에 넣는다.
5. 익은 토마토 수와 비어있는 토마토 칸 수를 더한 값이 최대이면 0을 출력한다.
5. 익은 토마토 주변을 돌면서
6. 안 익은 토마토가 있으면 현재 토마토가 익은 날에 +1을 해줘 저장해준다.
7. 그러면서 가장 늦게 익은 날을 max_num에 넣어준다.
8. 그러면서 count_one 값을 하나씩 올려준다.
9. count_one값이 ans값과 같으면 max_num에서 하루 빼서 출력하고
10. 아니면 -1 출력한다.

코드

from sys import stdin
from collections import deque

M,N,H = map(int, stdin.readline().split())
li = [[[0]*M for i in range(N)]for j in range(H)]
count_one = 0
count_minus =0
max_num = 1
queue = deque()

for i in range(H):
    for j in range(N):
        tmp = list(map(int, stdin.readline().split()))
        for k in range(M):
            li[i][j][k] = tmp[k]
            if tmp[k] == 1:
                queue.append((i,j,k))
                count_one +=1
            elif tmp[k] == -1:
                count_minus +=1

ans =M*N*H - count_minus

dx ,dy , dz = 	[1, -1, 0, 0, 0, 0], 
		[0, 0, 1, -1, 0, 0], 
		[0, 0, 0, 0, 1, -1]
        
if ans - count_one== 0 :
    print(0)
else:
    while queue:
        z, y, x = queue.popleft()

        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0<= nx < M and 0<=ny < N and 0 <= nz < H:
                if li[nz][ny][nx] == 0:
                    li[nz][ny][nx] = li[z][y][x] +1
                    max_num = max(li[nz][ny][nx],max_num)
                    count_one +=1
                    queue.append((nz,ny,nx))
        
    if count_one == ans:
        print(max_num -1)
    else:
        print(-1)
        

좋은 웹페이지 즐겨찾기