개구리

우물 안 개구리

3차원 그래프 문제다. 이미 익은 토마토를 기준으로 BFS를 실행하면서 총 소요되는 시간을 더해준다.

#토마토
from collections import deque
M,N,H = map(int, input().split())
tomato = []
already =[] #이미 익은 좌표
notready = 0 #인 익은 개수
for i in range(H):
    floor = []
    for j in range(N):
        
        line = list(map(int, input().split()))
        
        floor.append( line )
        
        for k in range(M):
            if line[k] == 1:
                already.append([i,j,k])
            elif line[k] == 0:
                notready+=1
        
    tomato.append(floor)

visited=[[ [0 for _ in range(M)] for _ in range(N) ] for _ in range(H)]
dx,dy,dh= [0,0,1,-1,0,0], [1,-1,0,0,0,0], [0,0,0,0,1,-1]

def BFS():
    global notready
    q=deque([])
    
    for tom in already:
        h,x,y = tom[0],tom[1],tom[2]
        visited[h][x][y]=1
        q.append(tom)
    
    tmp=0
    if q !=deque([]):
        idx =q[-1]
    
    while (q):
       
        h,x,y = q.popleft()
            
        for i in range(6):
            nH,nX,nY = h+dh[i], x+dx[i], y+dy[i]
            
            if 0<=nH<H and 0<=nX<N and 0<=nY<M :    
                if visited[nH][nX][nY]==0 and tomato[nH][nX][nY]==0:
                    visited[nH][nX][nY]=1
                    tomato[nH][nX][nY]=1
                    notready-=1
                    q.append([nH,nX,nY])
        
        if [h,x,y] == idx:
            tmp+=1
            if q !=deque([]):
                idx = q[-1]
            
    return tmp
            
                    
if notready==0:
    print(0)
else:
    sol = BFS()
    if notready>0:  
        print(-1)
    else:
        print(sol-1)

설계

입력값을 받으면서 이미 익은 토마토의 좌표를 already 배열에 담는다. 익지 않은 토마토는 개수만 notready에 저장해둔다.

2차원 그래프 탐색을 할 때와 마찬가지로 dx,dy,dh 배열을 만들어서 총 6번 반복문을 실행하면 좌,우,가로,세로, 위, 아래 방향을 모두 탐색할 수 있다.

구현

한 개의 토마토를 기준으로 주변의 토마토를 모두 탐색하면 +1일을 해야한다.

  1. 익지 않은 토마토의 개수가 0개라면 0을 출력하고 종료한다.
  2. 익지 않은 토마토가 있다면 BFS를 실행한다. 익은 토마토의 좌표를 모두 큐에 넣어준다.
  3. BFS를 실행하며 안익은 토마토를 모두 탐색한다.
  4. 한 개의 토마토를 기준으로 주변의 모든 토마토를 탐색했을 때 +1일을 하기 위해 큐의 마지막 원소를 idx로 설정한다.
  5. idx가 큐에서 pop되면 +1일로 계산하고 새로운 idx를 갱신한다.

ex) 인접한 토마토를 - 로 표현한다.

토마토 1, 1-1,1-2,1-3

토마토 2, 2-1,2-2,2-3,2-4

토마토 1-3-1, 1-3-2

토마토 2-2-1, 2-2-2

이를 큐에서 살펴보자.

1일차 큐 : [ 1, 2 ]

1일차 큐 : [2, 1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 2-4]

2일차 큐(1) : [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 2-4]

2일차 큐(2) : [ 2-1, 2-2, 2-3, 2-4, 1-3-1, 1-3-2]

2일차 큐(3) : [2-4, 1-3-1, 1-3-2, 2-2-1, 2-2-2]

3일차 큐 : [1-3-1, 1-3-2, 2-2-1, 2-2-2]

즉, 매 일마다 큐의 마지막 원소가 pop되면 +1일로 계산하면 된다.

다른 풀이

idx로 시간의 경과를 따로 계산하지 않고 visited 배열에 BFS가 진행됨에 따라 +1을 하며 시간의 경과를 저장하는 간단한 풀이 방법도 있었다.

댓글남기기

참고