[백준] 7576번 토마토 (Python)

문제

 

www.acmicpc.net/problem/7576

7576번: 토마토

 

코드

 

# 출력 : 토마토가 모두 익을 때까지의 최소날짜 출력
#        만약, 저장될 때 부터 모든 토마토가 익어있는 상태라면 0출력
#        토마토가 모두 익지는 못하는 상황이면 -1출력

from collections import deque
checker = True 
M, N   = list(map(int, input().split())) # M : 넓이 , N : 높이
tomato = [] 
for _ in range(N):
    tomato.append(list(map(int, input().split()))) # [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1]]


q = deque() # 익은 토마토를 담을 큐 생성

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1: # 익은 토마토 큐에 추가
            q.append([i,j]) # deque([[3,5]])


dx = [0,0,1,-1] 
dy = [1,-1,0,0]
# dx[0],dy[0] = (0,1) 오른쪽
# dx[1],dy[1] = (0,-1) 왼쪽
# dx[2],dy[2] = (1,0) 아래쪽
# dx[3],dy[3] = (-1,0) 위쪽

time = -1   # 출력값 : 걸린 날짜
            # -1로 시작하는 이유는 bfs로 검사 했을경우 이미 다 익은 토마토인 경우에는 걸린날짜 0을 리턴해주기 위함

# bfs   
def bfs(q, time):    
    while q: # 큐가 빌때 까지 계속 돌음
        time += 1 
        for _ in range(len(q)): # 큐에 길이만큼 반복 왜냐하면 익은 토마토가 여러개 있을 수 있기 때문에
            a, b = q.popleft()
            
            for i in range(4):  # 상하좌우 확인
                nx = a + dx[i]
                ny = b + dy[i]
                
                if (0 <= nx < N) and (0 <= ny < M) and tomato[nx][ny] == 0: # 범위가 안넘어가면서 안익은 토마토일 경우 큐에 추가하고 익혀줌
                    q.append([nx, ny])
                    tomato[nx][ny] = 1
    return time

time = bfs(q, time)
               

for i in tomato: # tomato = [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
    if 0 in i: # i안에 0이 있을경우는 토마토가 모두 익지 못한경우이다.
        checker = False
        print(-1) # -1 출력
        break

if checker:
    print(time)

 

코드설명

상자안에 토마토가 모두 익을 때 까지의 최소일수 출력

 

익은 토마토 주변으로 찾아나가야 하기 때문에 bfs로 풀 수 있다.

익은 토마토를 큐에 넣어주고 빼준 좌표를 기준으로 상하좌우를 모두 탐색해주고 범위안에 안익은 토마토가 있을시 큐에 넣어준뒤 tomato 리스트안에 값을 1로 변경해준다. 그리고 큐안에 값이 없을 때 까지 위 과정을 계속 반복한다.

 

tomato 리스트 안에 1개라도 0에 값이 있다면 모두 익지 못한 경우이기 때문에 -1을 출력한다.

 

그게 아니면 일수를 출력하면 된다.

 

다른풀이

import collections
m, n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
distance = [[0] * m for _ in range(n)]

queue = collections.deque()
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

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:
                if graph[nx][ny] == 0 and distance[nx][ny] == 0:
                    graph[nx][ny] = 1
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx,ny))

for x in range(n):
    for y in range(m):
        if graph[x][y] == 1:
            queue.append((x,y))

bfs()
checker = True
for i in graph:
    if 0 in i:
        print(-1)
        checker = False
        break

curMax = 0
for i in distance:
    curMax = max(curMax, max(i))

if checker:
    print(curMax)