토마토 BFS 풀이 설명

문제 "토마토(7576번)"는 보관 후 하루가 지나면 익지 않은 토마토가 익은 토마토의 영향을 받아 익게 되는 조건하에, 모든 토마토가 익을 때까지의 최소 일수를 구하는 문제입니다. 토마토는 2차원 배열 상자에 보관되며, 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없는 곳은 -1로 표현됩니다. 상자의 크기와 토마토의 배치 상태가 주어질 때, 모든 토마토가 익을 때까지의 최소 일수를 구하는 프로그램을 작성합니다. 만약 모든 토마토가 처음부터 익어있는 상태라면 0을, 모든 토마토가 익지 못하는 상황이면 -1을 출력합니다.

문제 해결 아이디어

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다. 익은 토마토의 위치를 시작점으로 하여 주변의 익지 않은 토마토를 익게 하는 과정을 반복합니다. 각 위치에 대해 (x, y) 좌표를 사용하며, 상, 하, 좌, 우의 네 방향에 대해 탐색을 진행합니다. 탐색을 진행하면서 각 토마토가 익는 데 걸리는 시간(일수)을 기록하며, 마지막에 익은 토마토 중 최대 일수를 결과로 출력합니다. 모든 공간을 탐색한 후에도 익지 않은 토마토가 있다면, 모든 토마토가 익지 못하는 상황이므로 -1을 출력합니다.

Python 코드

python
1from collections import deque
2
3def bfs():
4    while queue:
5        x, y = queue.popleft()
6        for i in range(4):
7            nx, ny = x + dx[i], y + dy[i]
8            if 0 <= nx < n and 0 <= ny < m and tomato[nx][ny] == 0:
9                tomato[nx][ny] = tomato[x][y] + 1
10                queue.append((nx, ny))
11
12m, n = map(int, input().split())
13tomato = [list(map(int, input().split())) for _ in range(n)]
14queue = deque()
15
16dx = [-1, 1, 0, 0]
17dy = [0, 0, -1, 1]
18
19for i in range(n):
20    for j in range(m):
21        if tomato[i][j] == 1:
22            queue.append((i, j))
23
24bfs()
25
26answer = 0
27for i in tomato:
28    for j in i:
29        if j == 0:
30            print(-1)
31            exit(0)
32    answer = max(answer, max(i))
33
34print(answer - 1)

이 코드는 2차원 배열에서 BFS를 이용하여 토마토가 모두 익는 데 필요한 최소 일수를 계산합니다. 각 토마토 위치를 큐에 저장하고, 익은 토마토의 주변을 탐색하면서 익지 않은 토마토를 익게 만듭니다. 모든 토마토가 익는 데 필요한 시간을 계산한 후, 모든 토마토가 익었는지 확인하고 결과를 출력합니다.

이제 추가적인 정보를 얻기 위해 관련 정보를 검색해보겠습니다.

그 외에 이 문제와 관련한 풀이 및 정보로는 다음과 같은 것들이 있습니다.

7576번: 토마토 : 백준 온라인 저지의 공식 문제 페이지입니다. 문제 내용과 다양한 사용자 제출 코드를 볼 수 있습니다.
[Baekjoon] 7576 - 토마토 BFS (Python) : 이 블로그 포스트에서는 Python을 사용하여 토마토 문제를 BFS 방식으로 해결하는 방법에 대해 설명하고 있습니다.
7576번 토마토 | BFS | Baekjoon BOJ 백준 7576 C++ 코드, 해설, 풀이 : C++로 문제를 해결하는 방법과 함께 풀이가 자세히 설명되어 있습니다.
[백준] 7576. 토마토 / python 파이썬 : 파이썬을 사용한 문제 해결 방법이 소개되어 있으며, BFS 알고리즘을 활용하는 방법에 대해 설명하고 있습니다.

추가적으로 궁금하신 점이 있다면 말씀해주세요!