[백준] 7569번 토마토 (python)

https://www.acmicpc.net/step/24

그래프와 순회 단계

 

1. 내가 작성한 코드

from collections import deque
import sys

input = sys.stdin.readline

m,n,h = map(int, input().split())

matrix = [[list(map(int, input().split())) for _ in range(n)]for _ in range(h)] #첫 상태

queue = deque()

for i in range(h):
  for j in range(n):
    for k in range(m):
      if matrix[i][j][k] == 1:
        queue.append((i,j,k)) #z,y,x순서서

def bfs():
  while queue:
  
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz = [0,0,0,0,-1,1]

    z,y,x = queue.popleft()
  

    for i in range(6):
      nx = x + dx[i]
      ny = y + dy[i]
      nz = z + dz[i]

      if nx<0 or ny<0 or nz<0 or nx>=m or ny>=n or nz>=h:
        continue
    
      if matrix[nz][ny][nx] == -1:
        continue

      if matrix[nz][ny][nx] == 0:
        matrix[nz][ny][nx] = matrix[z][y][x] + 1
        queue.append((nz,ny,nx))

bfs()

check = 0
result = 0

for i in range(h):
  for j in range(n):
    for k in range(m):
      if matrix[i][j][k] == 0:
        check +=1
        break
      else:
        result = max(result, max(matrix[i][j]))
        
if check != 0:
  print(-1)
else:
  print(result-1)

어제 풀었던 7576번과 유사하지만, 3차원으로 확장된 문제이다.

 

이 문제에서 가장 중요한 점은 좌표와 인덱스의 헷갈리지 않는 것이라고 생각한다.

 

 

 

2. 문제 해결 알고리즘

 

from collections import deque
import sys

input = sys.stdin.readline

m,n,h = map(int, input().split())

matrix = [[list(map(int, input().split())) for _ in range(n)]for _ in range(h)] #첫 상태

queue = deque()

1. bfs을 이용해서 deque 를 import한다. (deque를 사용하지 않고 구현하면 시간복잡도 박살난다는 소문이,,)

 

2. m,n,h(가로,세로,높이)를 import 받고, input값을 받아 matrix를 3차원으로 만든다. 

 

이 때, 헷갈릴 수 있는 것이 matrix[높이][세로][가로]이기 때문에

m은 input, split해서 list에 넣기 => n(세로)횟수 반복(층 한 개 완성하기)=> h(높이)횟수(전체 matrix 완성하기)순서로 받아야 한다.

 

for i in range(h):
  for j in range(n):
    for k in range(m):
      if matrix[i][j][k] == 1:
        queue.append((i,j,k)) #z,y,x순서

3. 현재 상태에 1인 애들을 queue에 삽입해준다.

 

위와 같이 matrix[높이][세로][가로] 이니 h,n,m 순서로 반복문을 돌린다.

 

def bfs():
  while queue:
  
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz = [0,0,0,0,-1,1]

    z,y,x = queue.popleft()
  

    for i in range(6):
      nx = x + dx[i]
      ny = y + dy[i]
      nz = z + dz[i]

 

4. bfs함수를 만들어준다. 6가지 방향이니 각각 앞,뒤,왼,오,위,아래 순서로 dx,dx,dz를 반복해주고

 

      if nx<0 or ny<0 or nz<0 or nx>=m or ny>=n or nz>=h:
        continue
    
      if matrix[nz][ny][nx] == -1:
        continue

      if matrix[nz][ny][nx] == 0:
        matrix[nz][ny][nx] = matrix[z][y][x] + 1
        queue.append((nz,ny,nx))

 

5. 새로운 좌표가 벽을 만나거나, 범위를 넘어가면 무시시켜준다. 그게 아닐 경우 valut값에 +1 해준 후 queue에 삽입해준다.

 

bfs()

check = 0
result = 0

for i in range(h):
  for j in range(n):
    for k in range(m):
      if matrix[i][j][k] == 0:
        check +=1
        break
      else:
        result = max(result, max(matrix[i][j]))
        
if check != 0:
  print(-1)
else:
  print(result-1)

 

6. bfs()를 실행시켜주고, matrix를 전체 탐색하며 0이 있으면 -1을 출력

 

0이 없으면, matrix가 가진 원소 중 제일 큰 값 -1(첫 날부터 +1 해줬으니)을 출력시켜 주면 된다.