[백준] 7576번 : 토마토

문제

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

풀이

[백준] 7576 : 토마토 🥇(골드5)
🎯 35.888%
⏰ 걸린 시간 : 40분

• 알고리즘 유형 : [BFS & DFS]

✅ 문제 요약

0. 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어 있지 않는 칸
1. 1을 기준으로 인접한 토마토가 익는다. (인접한 것 : 왼쪽, 오른쪽, 위, 아래)
2. 단, 1을 기준으로 익는 날짜는 동일하다.
3. 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 출력해라.

✅ 출력

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

✅ 풀이방법 & BFS 알고리즘로 푼 이유?

✔️ 트리 구조에서 Layer를 탐색하는 것이다. -> BFS에 적합하다.
0. 토마토는 1인 것에서 부터 익는것을 결정한다. 1이 여러개 일때 익는 시점은 같다.
1. Queue에 1인것 모두 다 넣고 Que를 빼주면서 시작하면 된다.

🔥 주의 : visited 필요 없다!
0. 바로 graph에 layer에 대한 가중치를 더해주면 된다.

코드(code)

import sys
from collections import deque

input = sys.stdin.readline
# M: 가로칸의 개수, N: 세로칸의 개수
M, N = map(int, input().split())

graph = [list(map(int, input().split())) for i in range(N)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
Que = deque()

# M(가로 : x ):6 N(세로, y):4
# 먼저 Que에 1인거 다 넣어주기 (익는 시점은 1이 있는게 다 동일하므로)
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            Que.append((i, j))
#BFS 시작
while Que:
    (x, y) = Que.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= N-1 and 0 <= ny <= M-1:
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                Que.append((nx, ny))

# 출력
day = 0
answer = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            answer = -1
            break
        else:
            day = max(day, graph[i][j])
if answer != -1:
    #날짜 1일부터 시작했으므로 
    answer = day-1
print(answer)

회고

BFS Layer를 표현하는 문제중에 하나이다.
트리 구조에서 같은 Layer를 표현하는 문제는 BFS로 풀 수 있다.

• BFS문제를 풀면서 더 익숙해져 보자

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/7576(%ED%86%A0%EB%A7%88%ED%86%A0).py