[DFS/BFS/완전탐색] ▲ 7569번 - 토마토

[백준] 7569번 - 토마토

풀이 시간: 1시간 이내

 

1) 문제 해결 아이디어

이전 문제(7576번)과 거의 동일한 문제로 이 문제도 BFS를 이용하여 답을 도출해 낼 수 있다.

로직 자체는 똑같기 때문에 3차원 리스트로 입력받고 잘 처리하기만 하면 쉽게 풀 수 있는 문제였다.

하지만 3차원 리스트를 입력받고 다루는데 익숙치 않아 조금 시간이 걸렸던 것 같다.

 

<이전 문제와 차이점>

	7576번	7579번
1	graph: 2차원 리스트	graph: 3차원 리스트
2	탐색 방향: 상하좌우(4개)	탐색 방향: 위, 아래, 왼쪽, 오른쪽, 앞, 뒤(6개)

 

2) 소스코드

from collections import deque

# 가로, 세로, 높이
m, n, h = map(int, input().split())
# 0: 안익음, 1: 익음, -1: 빈칸(3차원 리스트)
graph = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)] 
target = []  # 익은 토마토 위치
num = 0  # 안익은 토마토 개수

# 위,아래, 왼쪽, 오른쪽, 앞, 뒤
dx = [0, 0, 0, 0, -1, 1]
dy = [0, 0, -1, 1, 0, 0]
dz = [-1, 1, 0, 0, 0, 0]

# BFS
def bfs(target):
  queue = deque()
  # 시작 좌표들 삽입
  for i in target:
    queue.append(i)

  while queue:
    z, x, y = queue.popleft()
    # 6가지 방향 탐색
    for i in range(6):
      nx = x + dx[i]
      ny = y + dy[i]
      nz = z + dz[i]
      # 범위 내이고 익지 않은 토마토라면
      if(0 <= nz < h and 0 <= nx < n and 0 <= ny < m):
        if(graph[nz][nx][ny] == 0):
          # 삽입, 방문처리
          queue.append((nz, nx, ny))
          graph[nz][nx][ny] = graph[z][x][y] + 1


# 익은 토마토 좌표 찾기
for i in range(h):
  for j in range(n):
    for k in range(m):
      # 익은 토마토라면
      if(graph[i][j][k] == 1): 
        target.append((i, j, k))
      # 익지 않은 토마토라면
      elif(graph[i][j][k] == 0):
        num += 1  

# 1. 저장될 때부터 모든 토마토가 익었으면(0이 없으면)
if(num == 0):
  print(0)
else:
  bfs(target)
  
  for i in range(h):
    for j in range(n):
      # 2. 토마토가 모두 익지 못한다면(0이 있으면)  
      if(0 in graph[i][j]):
        print(-1)
        exit()
  
  # 3. 토마토가 모두 익었다면(0이 없으면)
  max = 0
  for i in range(h):
    for j in range(n):
      for k in range(m):
        if(graph[i][j][k] > max):
          max = graph[i][j][k]
  print(max - 1)

 

<3차원 리스트>

# 가로, 세로, 높이
m, n, h = 5, 3, 2 

# 3차원 리스트 생성
graph = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]

# 3차원 리스트 원소 접근(높이, 세로, 가로)
graph[0][1][2]	# 0
graph[0][1]	# [0, 0, 0, 0, 0]
graph[0] 	# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

 

 

[참고] https://dojang.io/mod/page/view.php?id=2297 

파이썬 코딩 도장: 23.6 연습문제: 3차원 리스트 만들기