토마토 (백준 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)
Author And Source
이 문제에 관하여(토마토 (백준 7659 -파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@grace0st/토마토-백준-7659-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)