7569번-토마토

uchan·2021년 7월 27일
0

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

이 문제는 https://www.acmicpc.net/problem/7576
의 업그레이드 버전인거 같다. 과거 단수 bfs만으로 풀었더 7576번 문제에서 살짝 코드를 변경해서 풀었다. 풀이과정은 다음과 같다

from collections import deque

m,n,h = map(int,input().split())
board = [None for _ in range(h)]
q = deque()
total_num = 0
reap_num = 0
for k in range(h):
    _board = []
    for i in range(n):
        temp = list(map(int,input().split()))
        for j in range(m):
            if temp[j]!=-1:
                total_num+=1
            if temp[j]==1:
                q.append(((k,i,j),0))
                
        _board.append(temp)
    board[k]= _board
d_list = [[1,0,0],[-1,0,0],[0,-1,0],[0,1,0],[0,0,-1],[0,0,1]]
visit = [[[False]*m for _ in range(n)] for _ in range(h)]
while q:
    (k,y,x),cnt = q.popleft()
    if visit[k][y][x]:
        continue
    visit[k][y][x]=True
    reap_num+=1
    for d in d_list:
        nk = k+d[0]
        ny = y+d[1]
        nx = x+d[2]
        if 0<=nk<h and 0<=ny<n and 0<=nx<m:
            if not visit[nk][ny][nx]:
                if board[nk][ny][nx]==0:
                    board[nk][ny][nx]=1
                    q.append(((nk,ny,nx),cnt+1))
if total_num!=reap_num:
    print(-1)
else:
    print(cnt)

일단 dy,dx가 아닌 dk,dy,dx로 3차원으로 움직여야된다. 그리고 모든 토마토를 일일히 검사하지 않고 개수를 세서 모두 익었는지 확인하면 끝!!

사실 3차원이여서 구현하기 까다로울 수 있으나 단순 bfs구현문제라서 난이도가 쉬운편에 속한다고 생각한다.

0개의 댓글