BFS - 토마토 [ 7569번 ]

처음에 무지성으로 아래의 코드 처럼 풀었더니 시간초과가 나왔다.

그도 그럴것이 For문 파티... 그럴만했다. ㅜ.ㅜ

 

어쨌든 한번 길을 잘못드니 계속 헤매는 느낌이 들었다.

금같은 시간은 계속 가기만하고,  풀이는 빙글빙글 돌기만 하고

from collections import deque
from copy import deepcopy

M, N, H = map(int, input().split())
dx = [1, 0, 0, -1, 0, 0]; dy = [0, 1, 0, 0, -1, 0]; dz = [0, 0, 1, 0, 0, -1]
graph = []
for _ in range(H):
    tmp = []
    for _ in range(N):
        tmp.append(list(map(int, input().split())))
    graph.append(tmp)
    
cnt = 0
while True:
    chk = False; yesRipe = False
    cpGraph = deepcopy(graph)
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if graph[i][j][k] == 0:
                    chk = True
                    for n in range(6):
                        nx = i+dx[n]; ny = j+dy[n]; nz = k+dz[n]
                        if 0<=nx<H and 0<=ny<N and 0<=nz<M and graph[nx][ny][nz] == 1:
                            cpGraph[i][j][k] = 1
                            yesRipe = True
                            break
                    
    graph = cpGraph
    
    # 안익은 토마토가 처음부터 없는 경우
    if chk == False and cnt == 0:
        print(0)
        break
    elif chk == False:
        print(cnt)
        break
    # 주변에 익은 토마토가 없어서 익을 수 없는 경우
    elif yesRipe == False:
        print(-1)
        break
    else:
        cnt += 1

 

다른 사람이 한 것을 참고하였다.

현재 내가 푼 문제는 3차원 배열인데, 아마 다른 토마토 문제중에 2차원 배열인 문제가 있는지 그 분의 풀이를 보게되었다.

그러면서 전에 다른 사람의 BFS 문제를 보면 볼 수 있었던 알고리즘 풀이법이 있었다.

 

예를 들면, 토마토가 익어가는 시간을 해당 토마토가 위치한 값으로 표현하는 방법이다.

이렇게 했을때, 토마토가 익었는지 확인이가능하다는 점 (0과 -1이 아니면 익은 토마토) 그리고 BFS를 통해 필요없는 곳까지 탐색할 필요는 없다는 점이 있다.

 

이런 사소한 것들에 대한 훈련이 아직은 많이 부족하다는 느낌이 들었다.

결국은 공식처럼 풀어지는 BFS, DFS 문제는 계속 익숙해지는 수 밖에 없는 것 같다.

from collections import deque
M, N, H = map(int, input().split())
graph = []
for _ in range(H):
    tmp = []
    for _ in range(N):
        tmp.append(list(map(int, input().split())))
    graph.append(tmp)
    
q = deque([])
yesallRipe = True
for i in range(H):
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 1:
                q.append((i, j, k))
            elif graph[i][j][k] == 0:
                yesallRipe = False
                
dx = [1, 0, 0, -1, 0, 0]; dy = [0, 1, 0, 0, -1, 0]; dz = [0, 0, 1, 0, 0, -1]   
while q:
    x, y, z = q.popleft()
    centerNum = graph[x][y][z]
    for n in range(6):
        nx = x+dx[n]; ny = y+dy[n]; nz = z+dz[n]
        if 0<=nx<H and 0<=ny<N and 0<=nz<M and graph[nx][ny][nz] == 0:
            graph[nx][ny][nz] = centerNum+1
            q.append((nx, ny, nz))
    
maxV = 0
noRipe = False
for i in range(H):
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 0:
                noRipe = True
            else:
                maxV = max(maxV, graph[i][j][k])
                
if yesallRipe:
    print(0)
elif noRipe:
    print(-1)
else:
    print(maxV-1)