백준 7569번 토마토

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #그래프 이론 #그래프 탐색 #너비 우선 탐색

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

---

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

예제 입출력 1

입력

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

출력

-1

---

예제 입출력 2

입력

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

출력

4

---

예제 입출력 3

입력

4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
1 1 1 -1

출력

0

---

코드(파이썬)

import sys
from collections import deque


def bfs(start):
    queue = deque(start)
    cnt = 0
    
    while True:
        for _ in range(len(queue)):
            s_h, s_r, s_c = queue.popleft()
            
            for next_h, next_r, next_c in [(d_h+s_h, d_r+s_r, d_c+s_c) for d_h, d_r, d_c in directions]:
                if 0 <= next_h <= h and 0 <= next_r < n and 0 <= next_c < m and\
                   containers[next_h][next_r][next_c] == 0:
                    containers[next_h][next_r][next_c] = 1
                    queue.append((next_h, next_r, next_c))
                    
        if queue:
            cnt += 1
        else:
            break
            
    return cnt


directions = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]
start = list()

m, n, h = map(int, sys.stdin.readline().split())
containers = [[list(map(int, sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]

if False in [all(0 not in line for line in floor) for floor in containers]:
    for h in range(h):
        for r in range(n):
            for c in range(m):
                if containers[h][r][c] == 1:
                    start.append((h, r, c))
    
    days = bfs(start)

    if True in [any(0 in line for line in floor) for floor in containers]:
        days = -1
else:
    days = 0

print(days)

---

특이사항

• 3차원에서의 BFS를 사용한 문제
  • 토마토 상태를 3차원 리스트에 저장
  • bfs 함수 내에서 큐 이용해 BFS 실행
  • 처음 시작 토마토를 찾기 위해 3중 for문 사용
  • BFS 부분이 아니라 안 익은 토마토 확인 부분에서 시간 초과 발생 -> all, any 함수 사용해 해결
• 내 코드(47,716KB, 2,972ms)에 비해 우수한 코드(바로가기, 56,680KB, 1,900ms)와 비교

  • import sys
    input = sys.stdin.readline
    
    m, n, h = map(int, input().split())
    db = []
    load = []
    cnt = 0
    res = -1
    
    for i in range(h):
        db.append([])
        for j in range(n):
            tmp = list(map(int, input().strip().split()))
            db[i].append(tmp)
            for k in range(m):
                if tmp[k] == 1:
                    load.append((i, j, k))
                elif tmp[k] == 0:
                    cnt += 1
    
    while load:
        res += 1
        tmp = []
    
        for i, j, k in load:
            if i > 0 and db[i - 1][j][k] == 0:
                db[i - 1][j][k] = 1
                tmp.append((i - 1, j, k))
            if j > 0 and db[i][j - 1][k] == 0:
                db[i][j - 1][k] = 1
                tmp.append((i, j - 1, k))
            if k > 0 and db[i][j][k - 1] == 0:
                db[i][j][k - 1] = 1
                tmp.append((i, j, k - 1))
            if i < h - 1 and db[i + 1][j][k] == 0:
                db[i + 1][j][k] = 1
                tmp.append((i + 1, j, k))
            if j < n - 1 and db[i][j + 1][k] == 0:
                db[i][j + 1][k] = 1
                tmp.append((i, j + 1, k))
            if k < m - 1 and db[i][j][k + 1] == 0:
                db[i][j][k + 1] = 1
                tmp.append((i, j, k + 1))
    
        cnt -= len(tmp)
        load = tmp
    
    print(-1 if cnt else res)
    

  • 토마토 창고 초기화 및 시작 토마토 지정
    • 기존: 초기화 및 시작 토마토 지정 분리
    • 개선: 반복문 하나로 수행

---

참고문헌

• “내장함수”, Python 3.10.2 문서, https://docs.python.org/ko/3/library/functions.html
• 붕어사랑, “파이썬 any, all 활용하기”, 붕어사랑 티스토리, https://lucky516.tistory.com/25