백준 7576번 토마토 (BFS 문제) _ 파이썬

from collections import deque

# 입력 받기
M, N = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(N)]

# 4방향(상, 하, 좌, 우) 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 익은 토마토의 위치 큐에 넣기
queue = deque()

# 초기 익은 토마토 위치 찾기
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:  # 익은 토마토일 경우
            queue.append((i, j))

# BFS 시작
def bfs():
    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        
        # 4방향 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            # 범위 체크
            if 0 <= nx < N and 0 <= ny < M:
                if tomato[nx][ny] == 0:  # 아직 익지 않은 토마토
                    tomato[nx][ny] = tomato[x][y] + 1  # 1초 증가시키면서 익히기
                    queue.append((nx, ny))  # 익은 토마토를 큐에 추가

# BFS 실행
bfs()

# 결과 확인: 토마토가 모두 익었는지 확인
max_days = 0
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 0:  # 아직 익지 않은 토마토가 있다면
            print(-1)
            exit(0)
        max_days = max(max_days, tomato[i][j])  # 가장 큰 값(최대 일수)을 구함

# 마지막에 -1을 빼줘야 0초부터 시작한 시간을 맞출 수 있음
print(max_days - 1)

---

1️⃣ 문제 이해하기

🔹 문제 요약

• 창고에 익은 토마토(1), 안 익은 토마토(0), 빈 칸(-1) 가 있다.
• 익은 토마토(1)는 하루가 지나면 상하좌우의 안 익은 토마토(0)를 익게 만든다.
• 모든 토마토가 익는 데 걸리는 최소 날짜를 구하는 문제!
  
  
  🔹 입력 예시

6 4  # 가로(열) M=6, 세로(행) N=4
0 0 -1 0 0 0
0 0  1 0 -1 0
0 0 -1 0 0 0
0 0  0 0 -1 1

🔹 출력 예시

4  # (모든 토마토가 익는 데 걸린 최소 날짜)

2️⃣ BFS를 사용하는 이유

• BFS(너비 우선 탐색) 는 최단 거리 탐색에 적합한 알고리즘이야.
• 토마토는 동시에 여러 방향(상하좌우)으로 퍼져나가야 함 → BFS 사용!
  (DFS는 한쪽으로만 깊게 탐색해서 적합하지 않아)

3️⃣ 문제 풀이 과정

✅ 1단계: 입력 받기

from collections import deque
import sys

M, N = map(int, sys.stdin.readline().split())  # 가로(M), 세로(N)
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

📌 이차원 배열(tomato)로 창고 정보를 저장

 

✅ 2단계: BFS를 위한 준비 (큐 초기화)

queue = deque()

# 익은 토마토(1)의 위치를 모두 큐에 추가
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append((i, j))

📌 익은 토마토(1)들의 위치를 미리 큐에 넣음 → BFS에서 동시에 퍼지게 하기 위해!

 

✅ 3단계: 4방향 이동 정의

dx = [-1, 1, 0, 0]  # 상, 하, 좌, 우 (행 방향)
dy = [0, 0, -1, 1]  # 상, 하, 좌, 우 (열 방향)

📌 현재 위치에서 상하좌우로 이동할 때 좌표를 쉽게 구하기 위해 사용!

 

✅ 4단계: BFS 탐색 시작

def bfs():
    while queue:
        x, y = queue.popleft()  # 큐에서 현재 위치 꺼냄

        for i in range(4):  # 네 방향 탐색
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 안에 있고, 익지 않은 토마토(0)일 경우
            if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[x][y] + 1  # 하루 추가
                queue.append((nx, ny))  # 새로운 익은 토마토 추가

📌 큐에서 꺼낸 좌표 (x, y)에서 상하좌우로 퍼져 나감
📌 익지 않은 토마토(0)를 발견하면 하루 추가 (tomato[x][y] + 1)

 

✅ 5단계: BFS 실행 후 최대 날짜 찾기

bfs()  # BFS 실행

max_day = 0  # 걸린 최대 일수
for row in tomato:
    for t in row:
        if t == 0:  # 익지 않은 토마토가 남아있으면
            print(-1)
            exit()
        max_day = max(max_day, t)

print(max_day - 1)  # 처음 시작을 1로 했으므로 1 빼줌

📌 모든 토마토가 익었는지 확인하고, 최대 날짜 출력!
📌 하나라도 0이 남아 있으면 -1 출력 (익을 수 없는 토마토 존재)
📌 처음 시작을 1로 설정했으므로, 결과에서 1을 빼줌!

4️⃣ 최종 코드

from collections import deque
import sys

# 입력 받기
M, N = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 큐 초기화 (익은 토마토 위치 저장)
queue = deque()
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append((i, j))

# 네 방향 이동 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 탐색 함수
def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[x][y] + 1
                queue.append((nx, ny))

bfs()  # BFS 실행

# 결과 계산
max_day = 0
for row in tomato:
    for t in row:
        if t == 0:
            print(-1)  # 익지 않은 토마토가 있으면 -1 출력
            exit()
        max_day = max(max_day, t)

print(max_day - 1)  # 처음 시작을 1로 했으므로 1 빼줌

5️⃣ 최종 정리

✅ BFS를 사용하는 이유

• 토마토가 동시에 상하좌우로 퍼져야 해서 BFS가 적합!

✅ 풀이 과정

1️⃣ 입력 받기 → 2차원 리스트(tomato) 생성
2️⃣ 큐 초기화 → 익은 토마토(1) 위치를 큐에 넣기
3️⃣ BFS 탐색 → 익은 토마토가 상하좌우로 퍼짐
4️⃣ 최대 날짜 찾기 → 모든 토마토가 익었는지 확인 후 출력