Baek_7569

원성혁·2022년 10월 5일
0

algorithm

목록 보기
4/21
post-thumbnail

class 4를 향해 토마토 문제를 풀었다.
대표적인 토마토 문제는 bfs 문제이고 이것 또한 구현 비슷하게 해야해서 어렵지는 않아보였다.
문제는 3차원이라 할일이 늘어났다...
4방향에서 6방향으로....

import sys
input = sys.stdin.readline
from collections import deque

m,n,h = map(int,input().split())
matrix = list()
dq = deque()
# visit = set()
tomato,bfs = 0,0
for k in range(h):
    tmp = list()
    for i in range(n):
        tmp.append(list(map(int,input().split())))
        for j in range(m):
            if tmp[i][j] == 1:
                dq.append((k,i,j))
                # visit.add((k,i,j))
                bfs+=1
                tomato+=1
            elif tmp[i][j] == 0:
                tomato+=1
    matrix.append(tmp)

ans = -1
while dq:
    for i in range(len(dq)):
        z,x,y = dq.popleft()
        for a,b,c in [[0,0,1],[0,0,-1],[1,0,0],[-1,0,0],[0,1,0],[0,-1,0]]:
            xa,yb,zc = x+a,y+b,z+c
            if 0<=xa<n and 0<=yb<m and 0<=zc<h and matrix[zc][xa][yb] == 0 and (zc,xa,yb) :
                dq.append((zc,xa,yb))
                matrix[zc][xa][yb] = 1
                # visit.add((zc,xa,yb))
                bfs+=1
    ans+=1
if bfs == tomato:
    print(ans)
else:
    print(-1)

처음에는 갔던곳을 visit으로 확인했는데ㅋ
이게 왜 이렇게 습관이 들었더라?? visit set을 사용하는 습관이 있는데
그렇게 짰는데 시간초과 났다ㅋ
그래서 0토마토를 1토마토로 바꿔주도록 해보니 성공~~
6방향은 첨해보는데 어렵지는 않았다.
그냥 구현이 귀찮다
암튼 bfs 이제 혼자힘으로 잘 짜니깐 스스로 뿌듯하다.

profile
AI개발자를 향해 전진중

0개의 댓글