728x90
반응형
문제:
2019/10/29 - [Algorithm/Python] - [BOJ]7576. 토마토
위 문제에서 더 발전한 문제로 이제 한 층이 아닌 여러 층에 대해서 토마토가 익는 것이 전이된다.
입력:
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2<=M<=100,2<=N<=100,1<=H<=100이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
출력:
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산하여 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
풀이방법:
이전문제에선 2차원 배열로 받았지만, 이번에는 3차원 배열로 작성한다. 또한 위, 아래로도 이동해야 하기 때문에 dx,dy,dn 세 가지 변수를 사용했다. 이외에는 이전문제와 동일한 풀이로 풀었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import sys
m,n,h=map(int,sys.stdin.readline().split())
tomatos=[]
for j in range(h):
temp=[]
for i in range(n):
t=list(map(int,sys.stdin.readline().split()))
temp.append(t)
tomatos.append(temp)
queue=[]
for k in range(h):
for i in range(n):
for j in range(m):
if tomatos[k][i][j]==1:
queue.append((k,i,j))
dx=[0,0,0,0,-1,1]
dy=[0,1,0,-1,0,0]
dh=[1,0,-1,0,0,0]
count=0
while len(queue)!=0:
count+=1
temp=[]
change=False
for k,i,j in queue[:]:
for c in range(6):
nx=j+dx[c]
ny=i+dy[c]
nh=k+dh[c]
if 0<= ny < n and 0<= nx < m and 0<=nh < h:
if tomatos[nh][ny][nx]==0:
tomatos[nh][ny][nx]=1
temp.append((nh,ny,nx))
change=True
queue.pop(0)
queue=temp
if not change:
break
remain=False
for k in range(h):
for i in range(n):
for j in range(m):
if tomatos[k][i][j]==0:
remain=True
break
if not remain:
print(count-1)
else:
print(-1)
|
cs |
문제링크:
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]14848. 정수 게임 (0) | 2019.11.04 |
|---|---|
| [BOJ] 1325. 효율적인 해킹 (0) | 2019.10.31 |
| [BOJ]7576. 토마토 (0) | 2019.10.29 |
| [BOJ]1049. 기타줄 (0) | 2019.10.18 |
| [BOJ]5567. 결혼식 (0) | 2019.10.17 |