백준 7569 토마토(3차원배열, BFS)

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

7569번: 토마토

상자에 있는 토마토가 근접해있는 다른 토마토에 영향이 가게 하는 것이니까 BFS로 접근하면 좋겠다는 생각을 했다.

여기서 첫번째 고려할점은 2차원이 아닌 3차원 방향이기 때문에 dx,dy,dz를 설정해줘야 한다는 것

dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

그 후 그래프를 돌면서 토마토가 들어있는 곳(1)을 찾으면 그 지점에서 bfs를 돌리면 된다고 생각해서 코딩을 했는데

이 생각은 완전히 잘못된 생각이다.

for z in range(h):
    for i in range(n):
        for j in range(m):
            if box[z][i][j] == 1:
                bfs(z,i,j)

이 방식으로 처음에 접근했고 한번의 탐색이 끝난 후 day +=1 을 해주는게 맞다고 생각했지만

box안에 있는 모든 토마토에 대해 모두 한번씩 6방향으로 처리를 해준 것이 하루가 지난 것 이기 때문에

box안에 있는 토마토(1)에 대한 좌표를 모두 기억해두었다가 그 토마토들을 모두 처리했을 때 day +=1를 하는게 맞다

위의 코드로 하면 5시방향에 있는 1들은 처리가 안된채로 day += 1이 되어버림

for z in range(h):
    for i in range(n):
        for j in range(m):
            if box[z][i][j] == 1:
                q.append((z,i,j))

토마토가 있는 좌표들을 모두 queue에 넣어주고 이 queue들을 가지고 bfs에 접근하면 모든 상황을 고려할 수 있게된다

 

 

1. 안익은 토마토 => 익은 토마토

def bfs(queue):
    global day
    while queue:
        day += 1
        for _ in range(len(queue)):
            z, x, y = queue.popleft()
            for i in range(6):
                nz = z + dz[i]
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nz < h and 0 <= nx < n  and 0 <= ny < m:
                    if not box[nz][nx][ny]:
                        box[nz][nx][ny] = 1
                        queue.append((nz,nx,ny))

모든 큐가 끝날때까지 탐색은 이루어져야 하니까 while로 감싸주고 그 때 당시의 queue안에 있는 좌표들이 끝날떄마다 day += 1을 해야하기 때문에 while문 안에서 for이 queue만큼 반복해서 이루어져야한다

 

 

2. day를 graph에 직접 더해주면서 마지막에 Max값으로 day추출

while(queue):
    x,y,z = queue.popleft()
    
    for i in range(6):
        a = x+dx[i]
        b = y+dy[i]
        c = z+dz[i]
        if 0<=a<h and 0<=b<n and 0<=c<m and graph[a][b][c]==0:
            queue.append([a,b,c])
            graph[a][b][c] = graph[x][y][z]+1
       
       
for i in graph:
    for j in i:
        for k in j:
            if k==0:
                print(-1)
                exit(0)
        day = max(day,max(j))

 

 

code

from collections import deque
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

def bfs(queue):
    global day
    while queue:
        day += 1
        for _ in range(len(queue)):
            z, x, y = queue.popleft()
            for i in range(6):
                nz = z + dz[i]
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nz < h and 0 <= nx < n  and 0 <= ny < m:
                    if not box[nz][nx][ny]:
                        box[nz][nx][ny] = 1
                        queue.append((nz,nx,ny))

m,n,h = list(map(int,input().split()))
box = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
day = 0
q=deque()

for z in range(h):
    for i in range(n):
        for j in range(m):
            if box[z][i][j] == 1:
                q.append((z,i,j))
bfs(q)

for z in range(h):
    for i in range(n):
        for j in range(m):
            if not box[z][i][j]:
                print(-1)
                exit(0)
print(day-1)