[BOJ] 백준 7576 토마토 / 너비 우선 탐색(BFS)

---

 

 

💣 문제 이해

 

 

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.

며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성한다.

 

너비 우선 탐색(BFS) 기법으로 풀이했다.

 

 

💭 풀이 과정

 

 

 

작성 언어: Python

from collections import deque


def bfs(t_m, t_n, t_box):
    day = -1
    mx = [-1, 1, 0, 0]
    my = [0, 0, -1, 1]

    while riped_index:
    	# 하루 씩 증가
        day += 1
        queue_size = len(riped_index)
        for _ in range(queue_size):
            x, y = riped_index.popleft()

            for k in range(4):
                nx = x + mx[k]
                ny = y + my[k]
                # 네 방향에 위치한 토마토들이 상자 범위 내에 있고, 안 익은 토마토인지 체크
                if 0 <= nx < t_n and 0 <= ny < t_m and t_box[nx][ny] == 0:
                    t_box[nx][ny] = 1
                    riped_index.append([nx, ny])

    # 여전히 안 익은 토마토가 남아있으면 -1을 출력, 아니면 최소 날짜 출력
    answer = sum(temp.count(0) for temp in t_box)
    return -1 if answer != 0 else day


m, n = map(int, sys.stdin.readline().split())
box = []
riped_index = deque()

# 입력 데이터 2차원 배열을 읽어오면서,
# 맨 처음 익은 토마토를 찾아서 위치를 riped_index 데크에 저장(큐를 대체)
for i in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(m):
        if row[j] == 1:
            riped_index.append([i, j])
    box.append(row)

print(bfs(m, n, box))

 

 

 

 

🏆 배운 점

 

 

BFS 개념이 적용되는 것을 직관적으로 잘 볼 수 있는 문제였던 것 같다.

 

역시 파이썬으로 구현하니 더욱 어려움을 덜 수 있었다. 👍 👍 👍