99클럽 코테 스터디 12일차 TIL: 3차원 BFS

오늘의 문제: 7569. 토마토

오늘 문제는 그래프의 대표적인 문제인 토마토이다. 토마토가 두 가지 버전이 있는데 그중에 3차원 형식으로 이루어진 문제이다. 3차원에서 그래프 탐색을 해야한다는 게 이 문제의 핵심이다.

 

확실히 3차원이 되다보니 아이디어가 쉽게 떠오르지 않아서 오늘은 검색 찬스를 쓰게 되었다… 아무래도 일반적인 그래프 탐색 방식이 아니라 그런지 쉽지 않았다. 노드와 간선으로 이루어진 그래프였으면 풀 수 있지 않았을까 싶기도 하다.

from collections import deque
m,n,h=map(int,input().split())
graph=[[[*map(int,input().split())] for i in range(n)] for j in range(h)]
visit=[[[-1]*m for i in range(n)] for j in range(h)]

deq=deque()
def check0(graph):
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k]==1 and visit[i][j][k]==-1:
                    deq.append((i,j,k))
                    visit[i][j][k]=1

def checkmax(graph):
    maxv=0
    for i in range(h):
        for j in range(n):
            for k in range(m):
                maxv=max(maxv,graph[i][j][k])
    return maxv

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

def bfs(graph):
    while deq:
        x,y,z=deq.popleft()
        for i in range(6):
            nx=x+dx[i]
            ny=y+dy[i]
            nz=z+dz[i]
            if nx<0 or nx>=h or ny<0 or ny>=n or nz<0 or nz>=m:
                continue    
            
            if graph[nx][ny][nz]==0 and visit[nx][ny][nz]==-1:
                deq.append((nx,ny,nz))
                graph[nx][ny][nz]=graph[x][y][z]+1
                visit[nx][ny][nz]=1

check0(graph)
bfs(graph)

for i in range(h):
    for j in range(n):
        for k in range(m):
            if graph[i][j][k]==0:
                print(-1)
                exit(0)
                
print(checkmax(graph)-1)

상당히 비효율적으로 문제를 풀었다. 검색 결과를 참고해서 했음에도 코드가 맘에 들지는 않는다. 그래도 그래프 형식이 아닌 문제에서 어떻게 상하좌우의 원소들에 접근할 수 있을지에 대한 아이디어를 얻은 듯 하다.

오늘의 회고

솔직히 회고라 할만한게 있을지 잘 모르겠다. 코드 퀄리티가 맘에 들지 않기도 하지만 이걸 다시 풀라고 했을 때 풀 수 있을지에 대한 의문이 든다. 아직 2차원 토마토도 안풀었었기 때문에 시간되면 한번 풀면서 상기해봐야겠다.