🔍 Problem

7576 토마토

---

⚡️ 사용한 알고리즘

---

📃 Input&Output

---

📒 해결 과정

1️⃣ 익은 토마토(1)의 좌표들을 전부 큐에 넣는다.
2️⃣ 큐가 빌때까지 다음을 반복한다.
	➊ 🧺 큐에서 현재 위치를 꺼낸다
	➋ 🔍 현재 위치에서 상, 하, 좌, 우 방향으로 이동 가능한 좌표를 확인한다
	➌ ✅ 이동 가능한 좌표가 있다면, 아래를 수행한다:
		① 해당좌표값이 익은 토마토(0)이면 
			1. 📝 해당 좌표의 값을 현재 "위치 값 + 1"로 갱신한다
        	→ 📏 이는 시간를 기록하기 위함이다

---

❗주의점

1. 토마토들이 익는 시간을 병렬적으로 생각할 필요가 없다. 왜냐하면 BFS왔다갔다 하면서 매트릭스에 각 토마토가 익는 시간을 기록해주기 때문이다.

---

💻 Code

import sys
from collections import deque

day = 0

# M :가로, N : 세로
M, N = map(int, sys.stdin.readline().split())



mat = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

que = deque([])

for i in range(N):
    for j in range(M):
        if mat[i][j] == 1:
            que.append((i, j))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx>=0 and ny>=0 and nx<N and ny<M:
                if mat[nx][ny]==0:
                    mat[nx][ny]=mat[x][y]+1
                    que.append((nx,ny))

bfs()
res=0
for i in mat:
    for j in i:
        if j==0:
            print(-1)
            exit(0)
        else:
            res=max(int(res),j)

res-=1

print(res)

---

🤔 느낀점

처음에 토마토가 여러개일 때 어떻게 병렬적으로 처리하지라는 1차원적인 생각을 하였지만 레퍼런스들을 보면서 bfs는 어차피 현재좌표를 알고 그에 따른 값(이 문제에서는 걸린 시간)을 알고있으니까 순차적으로 +1을 해주면서 다음좌표를 큐에 넣을 때, 현재시간 +1하는 방식으로 다음좌표의 시간을 기록해주면 되겠구나 하면서 풀었다. 많이 익숙해져야겠다는 생각이 들었다.

---

📝 출처

adore_voy