7569번: 토마토

7569번: 토마토

 

 

전형적인 BFS 문제다.

단, 이 문제에서 일반적인 BFS 문제와 다른 점은 3차원 리스트라는 점이다.

 

3차원 리스트긴 하지만 개념은 동일하기에, 큐 자료구조를 활용해 BFS를 구현했다.

 

---

# 7569번: 토마토
from collections import deque
import sys
input = sys.stdin.readline


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

box = [] # box를 저장하는 리스트
tomato = [] # 초기에 익은 토마토의 (x, y, h) 좌표를 저장하는 리스트
un_tomato_cnt = 0 # 초기에 익지 않은 토마토의 개수를 저장하는 변수
 
for k in range(h):
    each_box = [] # 한 층에 해당하는 박스
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(m):
            if data[j] == 1:
                tomato.append((i, j, k))
            elif data[j] == 0:
                un_tomato_cnt += 1
        each_box.append(data)
    box.append(each_box)

dx = [-1, 1, 0, 0] # x좌표 이동
dy = [0, 0, 1, -1] # y좌표 이동
dh = [-1, 1] # 다른 층으로 이동


# 큐
q = deque([tomato])

day = 0 # 토마토가 모두 익을 때까지 걸리는 최소 일수
while q:
    one_day = q.popleft() # 하루에 익은 토마토의 좌표들을 저장하고 있는 리스트 one_day
    one_day_tomato = [] # (하루에 추가될 익은 토마토의 x좌표, y좌표, 층수)를 저장하는 큐
    for one in one_day:
        x, y, floor = one # 현재 토마토의 x좌표, y좌표, 층수
        
        # 같은 층 토마토 익게 만들기
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                # 이미 익은 토마토라면 지나가기.
                if box[floor][nx][ny] == 1 or box[floor][nx][ny] == -1:
                    continue

                box[floor][nx][ny] = 1
                one_day_tomato.append((nx, ny, floor))
                un_tomato_cnt -= 1
        
        # 다른 층 토마토 익게 만들기
        for j in range(2):
            nh = floor + dh[j]

            if nh >= 0 and nh < h:
                if box[nh][x][y] == 1 or box[nh][x][y] == -1:
                    continue
                box[nh][x][y] = 1
                one_day_tomato.append((x, y, nh))
                un_tomato_cnt -= 1


        # 모든 토마토가 익었는지 확인 -> 모든 토마토가 익었다면 반복문 탈출
        if un_tomato_cnt == 0:
            break
    if len(one_day_tomato) > 0: # 만약 하루에 익게 만든 토마토가 있을 때만 큐에 하루에 익은 토마토를 저장하는 리스트 추가
        q.append(one_day_tomato)
    # 하루 경과
    day += 1


# 반복문을 탈출했는데 모든 토마토가 익었다면 day 출력
if un_tomato_cnt == 0:
    print(day - 1)
# 모든 토마토가 익지 않았다면 -1 출력
else:
    print(-1)

 

문제를 풀면서 당황했던 점은 2가지가 있었다.

 

첫번째는 토마토가 다 익었는지 여부를 어떻게 판단해야 될 지였다.

3차원 리스트 원소의 최대 개수는 100 * 100 * 100 = 100만개이므로 각 day마다 100만개의 반복문을 모두 돌아서 확인한다면 시간 초과확률 150퍼센트라고 생각했다.

그래서 고민하다가 처음에 리스트를 입력받을 때, 0(익지 않은 토마토)의 개수를 세는 방식으로 구현했다.

만약 0(익지 않은 토마토)의 개수가 0이 된다면, 모든 토마토가 익은 것이므로 그대로 반복문을 빠져나오면 된다.

 

두번째는 하루 경과 여부를 어떻게 판단해야 될 지였다.

원래는 큐 하나에 모든 (x, y, h) 좌표를  넣고, 큐를 확인할 때마다 day를 추가했다.

하지만 이 아이디어는 틀린 아이디어였다.

하루에 토마토가 여러 개 익으므로, 한 토마토를 확인할 때마다 day가 증가하는 게 아니다!

그래서 큐 안에 리스트를 넣어 구현했다.

큐에서 popleft를 통해 리스트 하나를 꺼내면, 그 리스트 안에 있는 토마토들은 하루에 익은 토마토이다.

그래서 해당 토마토를 모두 BFS를 통해 확인하고, 큐에 들어갈 토마토를 임시 리스트에 넣어서 다시 큐에 넣는다.

여기서 임시 리스트에 들어갈 토마토가 있을 때에만, 큐에 토마토 리스트를 넣을 수 있다.

 

 

 

 

 

시간이 생각보다 많이 걸려서 다른 풀이를 봤는데, 비슷한 시간인 걸로 보아 로직 자체는 문제 풀이에 적당한 것 같다.

더 많은 BFS/DFS 문제를 풀어봐야겠다.

 

 

 

---

 

[BOJ/백준] 7569번 토마토 (Python 파이썬)

BFS + Tabulation으로 이렇게 푸는 문제도 있다.

BFS가 종료되었을 때, 저장된 최댓값이 걸린 day 수이다.