[BOJ] 7569. 토마토

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

7569번: 토마토

 

 

1. 해결방법

BFS 문제인것은 보자마자 알 것이다.

다만 특징은 3차원이라는 것이다.
어떻게 할까?

map을 이용해서 2차원 배열을 만들고, 그것을 높이(H) 만큼 다시 for문으로 받으면 된다.

1. x, y, z방향의 디폴트 값을 설정
2. 시작하기 전 익은 토마토 위치 값을 q에 append
3. bfs를 돌면서 토마토가 익으면 day + 1하고 q.append
4. 전부 익지 않았을 경우에 3중 for문을 돌려서 인덱스 값이 0이 있다면 -1 print
5. 처음부터 전부 익은 토마토면 day가 0일 때 이미 q에 append 되었기 때문에 0이 print

 

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline


N, M, H = map(int, input().split())
graph = [[list(map(int, input().split())) for _ in range(M)] for _ in range(H)]

chk = [[[False] * N for _ in range(M)] for _ in range(H)]
dy, dx, dz = (-1, 1, 0, 0, 0, 0), (0, 0, -1, 1, 0, 0), (0, 0, 0, 0, -1, 1)


q = deque()

for k in range(H):
    for i in range(M):
        for j in range(N):
            if graph[k][i][j] == 1:
                chk[k][i][j] = True
                q.append(((k, i, j), 0))



def bfs():
    global answer

    while q:
        index, day = q.popleft()
        ez, ey, ex = index
        answer = day

        for d in range(6):
            ny = ey + dy[d]
            nx = ex + dx[d]
            nz = ez + dz[d]
            if 0 <= ny < M and 0 <= nx < N and 0 <= nz < H:
                if graph[nz][ny][nx] == 0:
                    graph[nz][ny][nx] = graph[ez][ey][ex] + 1
                    q.append(((nz, ny, nx), day + 1))


answer = 0
bfs()

for k in range(H):
    for i in range(M):
        for j in range(N):
            if graph[k][i][j] == 0:
                print(-1)
                exit(0)
else:
    print(answer)

 

 

3. 다른 사람 풀이

시간복잡도를 엄청나게 개선시킬 수 있다.

import sys
input = sys.stdin.readline

#bfs로 구현. 1이 여러 개 있으니 너비우선으로 동시에 탐색하는 것이 유리.

#입력 nxm=1000000(100만)
m,n,h=map(int,input().split())

l=[[ [-1 for i in range(m+2)] ] for i in range(h+2) ] #전체 리스트. 2차원->3차원. m,n,h 모두 상하좌우로 -1으로 감싸줘야함
for k in range(1,h+1):
    for i in range(n):
        tmp=list(map(int,input().split()))
        l[k].append([-1]+tmp+[-1])
for k in range(1,h+1):
    l[k].append([-1 for i in range(m+2)])
l[0]=[  [-1 for i in range(m+2)] for i in range(n+2) ]
l[-1]=[  [-1 for i in range(m+2)] for i in range(n+2) ]
#print(l)
#저장될 때부터 모든 토마토가 익어있는 상태 
zero=False
for i in l:
    for j in i:
        for k in j:
            if k==0:
                zero=True
                break
if zero==False: 
    print(0)
    exit(0)

#맨 처음 1인 부분
from collections import deque
q=deque()

for k in range(1,h+1):
    for i in range(1,n+1):
        for j in range(1,m+1):
            #print(k,i,j)
            if l[k][i][j]==1:
                q.append((k,i,j,1)) #x,y,c
#print(q)

def bfs():
    while True:
        if len(q)==0:
            break
        start=q.popleft()
        z=start[0]
        x=start[1]
        y=start[2]
        c=start[3]
        #print(start,q)
        if l[z][x][y-1]==0: #좌 #★BFS/DFS에서 어차피 움직일 수 있는 양은 모두 평등하기에, 덮어씌우는건 고려 안해도 된다★
            l[z][x][y-1]=c+1
            q.append((z,x,y-1,c+1))
        if l[z][x][y+1]==0: #우
            l[z][x][y+1]=c+1
            q.append((z,x,y+1,c+1))
        if l[z][x+1][y]==0: #앞
            l[z][x+1][y]=c+1
            q.append((z,x+1,y,c+1))
        if l[z][x-1][y]==0: #뒤
            l[z][x-1][y]=c+1
            q.append((z,x-1,y,c+1))
        if  l[z+1][x][y]==0:#위
            l[z+1][x][y]=c+1
            q.append((z+1,x,y,c+1))
        if  l[z-1][x][y]==0:#아래
            l[z-1][x][y]=c+1
            q.append((z-1,x,y,c+1))
                   
bfs()
maxx=0
for i in l:
    for j in i:
        for k in j:
            if k==0:  #토마토가 모두 익지는 못하는 상황, -1 출력
                print(-1)
                exit(0)
            elif k>maxx:
                maxx=k
print(maxx-1)