3 minute read

문제

접근 방법

전형적인 BFS 문제에 3차원 배열을 추가한 문제이다. 이 문제는 문제 푸는 방법이 어려웠던 것은 아니고 시간 초과를 해결하는것이 제일 어려웠다.

첫 접근 방법

나의 첫 풀이 방법은 모든 익은 토마토들의 좌표를 저장해놓고 하나씩 bfs를 하면서 익지 않은 토마토에 도달하는 최소 시간을 기록한 다음, 시간의 최대값을 구해서 며칠이 지나야지 토마토가 다 익는지 구하려고 하였다.

내 풀이 방법이 오래 걸린 이유는 우선 다음과 같다.

  • 방문한 토마토들을 다시 방문하지 않기 위해 bfs를 할 때마다 visited set을 만들어서 좌표들을 tuple로 저장했다.

    이때 생기는 문제는 visited 저장, 조회 등 모두 O(1) 이지만 값들을 해싱하는 과정과 tuple을 생성하는 과정이 모두 시간을 많이 쓴다는 것이다.

  • 모든 익은 토마토들을 하나씩 bfs을 하는 것이다.

    시간복잡도가 O(익은 토마토 수 T x 전체 칸 수 MNH)로 익은 토마토가 1000개가 넘는다면, O(1000x100x100x100)으로 1억이 된다.

내 첫 코드

import sys
from collections import deque
input = sys.stdin.readline
'''
모든 익은 것에 대해 bfs를 하여 각 칸에 도달하는 최소 시간을 구한다음 전체 시간의 최솟값을 구한다. 
time이 int(1e9)인 곳이 있다면 도달하지 못했다는 것이므로 이때는 -1을 출력
'''
m,n,h = map(int, input().split())

boxes = [[[] for _ in range(n)] for _ in range(h)]

time = [[[int(1e9)]*m for _ in range(n)] for _ in range(h)]
for h_i in range(h):
  for n_i in range(n):
    boxes[h_i][n_i] = list(map(int, input().split()))


ready = set()
readies = 0
empties = 0
moves = [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0),(0,0,1),(0,0,-1)]

'''
모든 토마토들이 익었는지 확인하는 부분
'''
for i in range(h):
  for j in range(n):
    for k in range(m):
      if boxes[i][j][k] == 1:
        readies +=1
        ready.add((i,j,k))
      elif boxes[i][j][k] == -1:
        empties+=1
if (readies + empties) == m*n*h:
  print(0)
  
# bfs 진행
else:
  for height,row,width in ready:
    q = deque()
    q.append((height,row,width,0))
    visited = set()
    visited.add((height,row,width))
    while q:
      hi,ri,wi,t = q.popleft()
      for dh,dr,dw in moves:
        new_hi, new_ri, new_wi = hi+dh, ri+dr, wi+dw
        if 0<=new_hi<h and 0<=new_wi<m and 0<=new_ri<n and boxes[new_hi][new_ri][new_wi] == 0 and (new_hi, new_ri, new_wi) not in visited:
          time[new_hi][new_ri][new_wi] = min(time[new_hi][new_ri][new_wi], t+1)
          q.append((new_hi, new_ri, new_wi, t+1))
          visited.add((new_hi, new_ri, new_wi))

'''
총 걸린 시간 확인하는 코드
'''
  max_val = 0
  for i in range(h):
    for j in range(n):
      for k in range(m):
        if (i,j,k) not in ready:
          max_val = max(max_val, time[i][j][k])
  
  if max_val == int(1e9):
    print(-1)
  else:
    print(max_val)

옳은 접근 방법

따라서 얻은 해결책이 익은 토마토들을 하나씩 bfs하지 말고 익은 토마토들을 다 q에 넣어서 bfs를 진해야하였다. 이렇게 함으로써 오직 O(N x M x H)의 시간이 걸리게 된다.

그리고 시간을 더 단축하기 위해 visited 배열을 아예 사용하지 않고 bfs를 진행할 때도 def 문으로 함수를 구현하여 구현했다. 이렇게 하면 시간이 더 빨라진다고 한다.

정답 코드


import sys
from collections import deque
input = sys.stdin.readline
'''
모든 익은 것에 대해 동시에 bfs를 하여 각 칸에 도달하는 최소 시간을 구한다. 
토마토이면서 아직 방문이 안 된 곳이 있다면 -1을 출력
방문 기록은 boxes 값이 1 이상이면 방문, 0이면 미방문으로 기록했다.
'''
m,n,h = map(int, input().split())

boxes = [[[] for _ in range(n)] for _ in range(h)]

for h_i in range(h):
  for n_i in range(n):
    boxes[h_i][n_i] = list(map(int, input().split()))

ready = []
moves = [[1,0,0], [-1,0,0], [0,1,0], [0,-1,0],[0,0,1],[0,0,-1]]

for i in range(h):
  for j in range(n):
    for k in range(m):
      if boxes[i][j][k] == 1:
        ready.append((i,j,k))
        
#익은 토마토들에 대해서 동시에 bfs 진행
def bfs(tomatoes):
  q = deque(tomatoes)
  while q:
    hi,ri,wi = q.popleft()
    for dh,dr,dw in moves:
      new_hi, new_ri, new_wi = hi+dh, ri+dr, wi+dw
      if 0<=new_hi<h and 0<=new_wi<m and 0<=new_ri<n and boxes[new_hi][new_ri][new_wi] == 0:
        q.append([new_hi, new_ri, new_wi])
        boxes[new_hi][new_ri][new_wi] = boxes[hi][ri][wi]+1
        
bfs(ready)

max_val = 0
poss = True

for i in range(h):
  if not poss: 
    break
  for j in range(n):
    if not poss: 
      break
    for k in range(m):
      #다 도달하는데 걸리는 최소시간의 최대값 구하기
      max_val = max(max_val, boxes[i][j][k])
      # bfs를 했는데도 0이라면 방문이 불가능한 것이다.
      if boxes[i][j][k]==0:
        poss = False
        break
  

if not poss:
  print(-1)

else:
  print(max_val-1)

배운 것

  • 여러 개의 시작점에 대해서 bfs를 해야할 때는 bfs의 queue에 모든 시작점들을 다 넣으면 시간이 훨씬 줄어든다는 것이다

  • 동일한 O(1)이지만 visited을 기록할 때, set보다는 배열을 만드는 것이 더 유리하다는 것이다.

  • 알고리즘을 함수로 구현하는것이 파이썬에서 더 빠르다.

You May Also Enjoy