[백준] 7569번 토마토 - (Python)

https://www.acmicpc.net/problem/7569

7569번: 토마토

DFS, BFS를 이용하여 구현하는 그래프 문제. 단, 기존의 그래프문제와 살짝 다른 점은 3차원 공간상에서 문제를 해결해야 합니다. 2차원에서 해결하는 토마토 문제를 잘 해결하셨다면, 해당문제를 푸는데 크게 어려움은 없을 거 같습니다. 공간을 3차원으로 만들어주고, BFS를 이용하여, 각 상하좌우위아래로 움직여주면 됩니다.

※ 고려사항

1. 3차원 입력

2. BFS

3. 출력

---

1. 3차원 입력

Python list에서의 3차원 행렬은 3개의 index를 받습니다. 높이, 행, 열 순서로 인덱싱하기 때문에, 이 점만 유의해주면 됩니다. 자세한 내용은 '파이썬 3차원 배열'을 참고해 주세요!

출력은 다음과 같습니다.

import sys
from collections import deque

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)]

day = 0

 

2. BFS

해당문제는 BFS를 이용하여 간단하게 구현할 수 있습니다. 그렇기 때문에 Queue를 생성해줘야 합니다. 재귀구현은 시간초과를 발생시키므로, Queue를 생성한 후, 토마토가 있는 행렬의 좌표를 Queue에 삽입합니다.

이 Queue를 BFS를 통해 각각의 방향으로 이동시킨 후, 해당 범위 내에서 익지 않은 토마토를 만나게 되면, 해당위치를 Queue에 다시 삽입하여 Queue가 완전히 empty가 될 때까지 반복합니다.

날짜는 이동시키기 전 위치의 +1 값을 이동된 위치에 저장합니다. 이렇게 되면, 움직인 좌표의 날짜는 모두 동일하게 교체됩니다. 코드는 다음과 같습니다.

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])

# 이동변수
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

def bfs():
    while queue:
        
        # x, y, z 할당
        z, y, x = queue.popleft()

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

            # 범위내에 존재하면서 익지않은 토마토 만나면 1 증가
            if 0 <= nx < m and 0 <= ny < n and  0 <= nz < h and matrix[nz][ny][nx] == 0:
                matrix[nz][ny][nx] = matrix[z][y][x] + 1
                queue.append([nz, ny, nx])

 

3. 출력

출력의 경우 모든 행렬을 검색한 후, 최대의 day를 찾으면 됩니다. 만약, 이 과정에서 익지 않은 토마토를 발견하게 되면 -1을 출력하고, 종료합니다.

코드는 다음과 같습니다.

# 모든 토마토 확인
for i in range(h):
    for j in range(n):
        for k in range(m):

            # 익지 않은 토마토 존재하면 -1
            if matrix[i][j][k] == 0:
                print(-1)
                exit(0)
            else:
                # 최대일수 저장
                day = max(day, matrix[i][j][k])

# 첫 시작일수 빼기
print(day - 1)

---

전체코드

import sys
from collections import deque

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)]

day = 0

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])

# 이동변수
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]

def bfs():
    while queue:
        
        # x, y, z 할당
        z, y, x = queue.popleft()

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

            # 범위내에 존재하면서 익지않은 토마토 만나면 1 증가
            if 0 <= nx < m and 0 <= ny < n and  0 <= nz < h and matrix[nz][ny][nx] == 0:
                matrix[nz][ny][nx] = matrix[z][y][x] + 1
                queue.append([nz, ny, nx])
bfs()

# 모든 토마토 확인
for i in range(h):
    for j in range(n):
        for k in range(m):

            # 익지 않은 토마토 존재하면 -1
            if matrix[i][j][k] == 0:
                print(-1)
                exit(0)
            else:
                # 최대일수 저장
                day = max(day, matrix[i][j][k])

# 첫 시작일수 빼기
print(day - 1)

 

---

3차원 공간에서의 문제만 해결해 주면, 크게 어렵지 않게 접근할 수 있었던 그래프 문제입니다. 앞 포스팅에서 말씀드렸듯이 단순 BFS, DFS는 반복해서 하다 보면 문제를 쉽게 해결할 수 있습니다. 좀 더 다양한 그래프 알고리즘으로 돌아오겠습니다.

설명의 오류나, 궁금하신 점은 언제든 피드백해 주시면 감사하겠습니다 ^~^