문제 출처 : https://www.acmicpc.net/problem/7576
난이도 : 골드 5

---

문제 파악

토마토 상자에서
1 : 익은 토마토
0 : 안 익은 토마토
-1 : 토마토 없음

익은 토마토(1)는 하루가 지나면 상하좌우(4방향)로 인접한 안 익은 토마토(0)를 익게 만든다.
"모든 토마토가 익는 데 걸리는 최소 일수"를 출력해야 한다.

핵심 포인트:

• 익은 토마토가 여러 개일 수 있다.
• 동시에 퍼져나가야 "최소 일수"가 된다.
  => 여러 시작점에서 동시에 BFS (Multi-source BFS)

---

"최소 일수" + "인접으로 전파" = BFS 냄새가 강하다.

근데 시작점(익은 토마토)이 여러 개다.
각각 BFS를 따로 돌리면 날짜 계산이 꼬일 수 있음.

그래서:

• 처음부터 익어있는 모든 좌표(1)를 큐에 한 번에 넣고 BFS 시작
• 큐에 들어간 순서대로 퍼지면 "같은 날짜의 전파"가 자연스럽게 처리된다.

날짜(일수) 기록 방법:

• graph 자체에 날짜를 누적시킨다.
• 처음 익은 토마토는 1
• 어떤 칸이 익을 때: graph[ny][nx] = graph[y][x] + 1
• 최종 최대값 - 1이 "걸린 일수"

---

해답 및 풀이

from collections import deque
import sys
input = sys.stdin.readline


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

# M : 가로, N : 세로
M,N = map(int,input().split())


#.정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸
graph = []
for _ in range(N):
    graph.append(list((map(int,input().split()))))


def bfs(graph,M,N):
    queue = deque()

    # 익은  토마토 전부 큐에 넣기
    for y in range(N):
        for x in range(M):
            if graph[y][x] == 1:
                queue.append((x,y))

        # BFS 전파
    while queue:
        x, y = queue.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((nx, ny))

    # BFS 다 돌고, 결과 계산
    min_day = 1
    for y in range(N):
        for x in range(M):
            # 아직 0인 토마토가 있으면 -1 리턴
            if graph[y][x] == 0:
                return -1
            
            # 최소일수 더 큰게 발견될때마다 초기화
            if graph[y][x] > min_day:
                min_day = graph[y][x]
    
    return min_day - 1 # 3이라면 시작이 1이기때문에 2가 정답이라

print(bfs(graph,M,N))

---

다음날 푼 코드

import sys
from collections import deque
input = sys.stdin.readline

# 방향벡터, 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# M 가로, N 세로
M, N = map(int,input().split())

box = []
queue = deque()

for _ in range(N):
    box.append(list(map(int,input().split())))

# box
# [[1, -1, 0, 0, 0, 0], 
# [0, -1, 0, 0, 0, 0], 
# [0, 0, 0, 0, -1, 0], 
# [0, 0, 0, 0, -1, 1]]

# box 이중반복문으로 탐색하여 1인 토마토, 인덱스값 큐에 넣기
for row_index in range(N): # 4 
    for col_index in range(M): # 6 
        if box[row_index][col_index] == 1:
            queue.append((row_index,col_index))

# queue
# deque([(0, 0), (3, 5)])


# BFS
while queue:
    x,y = queue.popleft()

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]

        if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0:
            box[nx][ny] = box[x][y] + 1
            queue.append((nx,ny))

min_day = 1
for x in range(N):
    for y in range(M):
        # 아직 0인 토마토가 있으면 -1
        if box[x][y] == 0:
            print(-1)
            sys.exit(0)
        
        if box[x][y] > min_day:
            min_day = box[x][y]

print(min_day-1)

min_day 로직을 처리하지 못했다.
내일 다시

다다음날 푼 코드

import sys
input = sys.stdin.readline
from collections import deque

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


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

box = []

for _ in range(N):
    box.append(list(map(int,input().split())))

# 큐에 익은 토마토(1) 찾아서 넣기
queue = deque() # 큐 생성

# M,N 이 1000 이하라 이중 반복문 완전 탐색 가능
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            queue.append((i,j))

# BFS
while queue:
    y, x = queue.popleft() # 세로, 가로

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]

        if 0 <= nx <  M and 0 <= ny < N and box[ny][nx] == 0: # 범위 내 존재, 아직 안익은 토마토(0) 이라면
            box[ny][nx] = box[y][x] + 1 # 하루 추가
            queue.append((ny,nx)) # 그 익은 토마토 좌표(1) 큐에 추가

# 여기까지 오면 box가 다 끝까지 반복 돈 것임

# 이제 검사
min_day = 0
for i in range(N):
    for j in range(M):
        if box[i][j] == 0: # 다 돌았는데도 안 익은 토마토(0) 가 있다면 -1 을 출력
            print(-1)
            sys.exit(0) # 프로그램 끝내기
        
        # 모든 토마토가 익었다면
        min_day = max(min_day, box[i][j])


print(min_day-1)

i,j y,x, row, col 등등 가로 세로 개념이 점점 익숙해지는 것 같다.