[백준] 7576 토마토 (파이썬/python)

🎈문제

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

 

🎁어떤 알고리즘?

1. 인접한 칸을 익게 만든다고 했으므로 당연히 bfs를 사용한다. (bfs란?)

2. 이 문제와 같이 시작점이 여러개인 문제는 큐에 시작점을 모두 넣고 나서 bfs를 돌리는 것이 핵심이다.

 

💻코드

from collections import deque

def bfs():
    # 상하좌우 좌표 설정
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    while deq:
        x,y = deq.popleft() # 큐에서 익은 토마토 좌표 꺼내기      
        for i in range(4):  # 상하좌우 탐색 시작
            nx = x + dx[i]
            ny = y + dy[i]
            # graph 벗어난 좌표는 무시
            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            if graph[nx][ny] == 0:  # 안익은 토마토 발견
                graph[nx][ny] = graph[x][y] + 1 # 날짜+1함으로써 익은 상태로 만들기
                deq.append([nx,ny])

# n: 세로(x), m: 가로(y)
m,n = map(int,input().split())

#graph
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))


deq = deque()   # 큐 설정

# 탐색 시작, 익은 토마토 좌표 큐에 넣어놓기
#(0:안익은 토마토, 1:익은 토마토)
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            deq.append([i,j])

# bfs돌려서 토마토 익히기
bfs()

# 익지 못하는 토마토 확인 및 걸리는 날짜 확인
all_ripe = True # 토마토가 모두 익었는지 확인할 변수
day = 0 # 토마토가 모두 익을 때까지의 최소 날짜

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:    # 아직 안익은 토마토가 존재하면
            all_ripe = False    
            print(-1)
            break
        day = max(day,graph[i][j])
    if not all_ripe:
        break

if all_ripe:    # 토마토 모두 익었으면
    print(day-1)