백준/ Gold 5 문제 , 백준 파이썬 7569, 토마토 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 7569, 토마토 [BFS]

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
이전 7576 번 토마토 문제에서 층이 생긴 문제. 즉, 3차원 배열가지고 풀어야한다.

 

<문제 출처>

 

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

7569번: 토마토

------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-5-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-7576-%ED%86%A0%EB%A7%88%ED%86%A0

백준/ Gold 5 문제 , 백준 파이썬 7576 , 토마토 [BFS]

 

이전 토마토 문제에서 옵션이 더 추가된 문제이다.

 

크게 어려워진 점은 없으며, 층을 구분할 수 있게 upDown=[0,1,-1] 코드를 추가시켜줬다.

 

차례로, 같은층, 위층, 아래층 으로 이동시켜준다

 

 

bfs 함수내 for 문 i 가 0일경우는 같은 층일경우 이므로 상하좌우를 확인해주고

 

i가 1일 경우 바로 윗칸, 2일 경우 바로 아랫칸을 확인한다.

 

 

최종 box 배열에서 0 이 남아있을 경우 -1 출력

 

만약 2 이상의 숫자가 하나도 없을 경우 토마토가 주변으로 익어나아가지 않은 경우이므로 0 을 출력시킨다.

 

이외에는 배열에서 가장 큰 숫자를 구해 -1 한 값을 출력시키면 된다.

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

from collections import deque

vertical=[1,-1,0,0] 
parallel=[0,0,1,-1]
upDown=[0,1,-1]  # 같은층, 위층, 아래층
box=[]
dq=deque()
M,N,H=map(int,input().split())
cnt=0
def bfs():
    global cnt
    while dq:
        z,x,y=dq.popleft()
        for i in range(3):
            if i==0:
                # 같은 층 확인
                for j in range(4):
                    move_x=x+vertical[j]
                    move_y=y+parallel[j]
                    if 0<=move_x<N and 0<=move_y<M:
                        if box[z][move_x][move_y]==0:
                            box[z][move_x][move_y]=box[z][x][y]+1
                            dq.append([z,move_x,move_y])
            else:
                # 위층, 아래층 확인
                for k in range(1,3):
                    move_z=z+upDown[k]
                    if 0<=move_z<H:
                        if box[move_z][x][y]==0:
                            box[move_z][x][y]=box[z][x][y]+1
                            dq.append([move_z,x,y])
for _ in range(H):
    tmp=[]
    for _ in range(N):
        tmp.append(list(map(int,input().split())))
    box.append(tmp)

# dq에 우선 1의 위치들을 모두 저장해 둔다.
for i in range(H):    
    for j in range(N):
        for k in range(M):
            if box[i][j][k]==1:
                dq.append([i,j,k])
bfs()
check=False
MAX=0

for i in range(H):
    for j in range(N):
        for k in box[i][j]:
            # 익지 않은 토마토가 1개라도 있을 경우
            if k==0:
                print(-1)
                exit(0)
            # 처음이랑 배열이 똑같은 경우. 즉, 토마토가 1개도 익어나아가지 않음.
            if k==2:
                check=True
            if k>MAX:
                MAX=k
if check==False:
    print(0)
else:
    print(MAX-1)