99클럽 코테 스터디 12일차 TIL / BFS(너비 우선 탐색)

✏️ 문제

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

 

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

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

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

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 G5

✅ 소요 시간: 54분

✅ 권장 시간: 1시간 15분

 

👩‍🏫 참고

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

 

💡 풀이

1) 문제 유형 파악

7576번 토마토 문제에 층수 개념이 추가된 문제라 7576번 문제와 동일하게 BFS로 구현했다.

 

2) 유의사항

일반적인 BFS 문제 풀이에서 크게 벗어나는 건 없었지만 배열 차원이 하나 늘다 보니까 신경 써야 할 부분이 몇 개 있었다.

 

① 3차원 배열 선언

2차원 이상의 배열을 다루는 데 약한 편이라 입력으로 주어지는 토마토 정보를 받아서 밭 전체를 구성하는 것부터 살짝 헷갈렸다. 높이를 나타내는 인덱스가 가장 앞에 오기 때문에 farm[층 인덱스][행 인덱스][열 인덱스]로 접근해야 함!

 

② 모든 토마토가 다 익어있는 경우 처리

모든 토마토가 이미 다 익은 상태라 익힐 필요가 없는 경우 0을 출력해야 한다. 이 부분을 처리하기 위해 아래와 같은 과정을 거쳤다.

 

1️⃣ 행 단위로 0이 포함되어 있는지 확인하고 0이 포함되어 있지 않은 행이면 all_ripe라는 변수 값+1

2️⃣ all_ripe 값이 토마토 밭의 전체 행 개수 N*H(한 층에 행이 N개이기 때문)와 동일하면 0 출력

 

③ 좌표 이동용 배열 선언

2차원 배열에서 BFS 문제를 풀 때는 상하좌우 네 방향으로 움직일 수 있게 dx, dy 배열을 정의했는데 여기서는 dz 배열을 추가해서 층을 옮겨 다니는 것을 구현했다.

 

이외에 다른 부분은 모두 7576번과 똑같이 처리해줬다.

 

3) 구현

import sys

from collections import deque

input = sys.stdin.readline

M, N, H = map(int, input().split())

farm = []

for _ in range(H):
    tomato = []
    
    for _ in range(N):
        tomato.append(list(map(int, input().split())))
    
    farm.append(tomato)
    
all_ripe = 0

ripen_tomato = deque()

day = [[[0]*M for _ in range(N)] for _ in range(H)]

for h in range(0, len(farm)):
    for r in range(0, len(farm[h])):
        if 0 not in farm[h][r]:
            all_ripe += 1
        
        for c in range(0, len(farm[h][r])):
            if farm[h][r][c] == 1:
                ripen_tomato.append((h, r, c))
            elif farm[h][r][c] == -1:
                day[h][r][c] = -1

if all_ripe == N*H:
    print(0)
else:
    dx = [1, -1, 0, 0, 0, 0]  # x축 -> 오른쪽, 왼쪽
    dy = [0, 0, 1, -1, 0, 0]  # y축 -> 아래, 위
    dz = [0, 0, 0, 0, 1, -1]  # z축 -> 앞, 뒤
        
    while ripen_tomato:
        h, r, c = ripen_tomato.popleft()
        
        for i in range(6):
            new_h, new_r, new_c = h+dz[i], r+dx[i], c+dy[i]
            
            if (0 <= new_h < H and 0 <= new_r < N and 0 <= new_c < M) and farm[new_h][new_r][new_c] == 0:
                farm[new_h][new_r][new_c] = farm[h][r][c]+1
                
                ripen_tomato.append((new_h, new_r, new_c))

    day = 0

    for height in farm:
        for row in height:
            if 0 in row:
                print(-1)
                exit()

            day = max(day, max(row))

    print(day-1)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 3차원 배열 다루기 ⭐ 연습장에 배열 그림 그리고 손으로 써가면서 풀었다..^^

❗ 배운 점

• 2차원 이상의 배열 요소에 접근할 때는 추가된 차원을 제일 앞으로 보내서 생각하면 된다.