[백준][7576][python] 토마토 - BFS

7576번: 토마토

 

출발지가 여러개인 bfs 문제이다.

박스 안에 토마토의 상태를 -1, 0, 1로 표현하고 (-1 : 토마토 없음. 0 : 안익은 토마토. 1: 익은 토마토)

토마토가 전부 익을때 까지 걸리는 일수를 구한다.

익은 토마토는 하루에 상하좌우 한 칸씩 영향을 미쳐 주변 토마토가 익게한다.

풀이과정

값 입력 및 변수 초기화

from collections import deque

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

M, N = map(int, input().split())
box = []
tomato_q = deque()

for i in range(N):
    line = list(map(int, input().split()))
    for j, l in enumerate(line) :
        if l == 1:
            tomato_q.append([i,j])
    box.append(line)

토마토가 있는 위치에서 상하좌우로 한 칸씩 이동하며 주변을 체크해야하므로 dx, dy를 설정해주었다.
또 토마토 위치를 입력받으면서 익은 토마토(1)의 위치를 큐에 넣어주었다.

 

토마토 익는 기간 체크

while len(tomato_q) > 0 :
    x, y = tomato_q.popleft()
    day = box[x][y]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0 :
            box[nx][ny] = day + 1
            tomato_q.append([nx, ny])

큐가 빌어있을 때 까지 반복문을 돌며 주변 박스를 체크해주었다.
nx, ny가 범위 내에 인덱스이고, 안익은 토마토일때(0)
box위치에 이전 토마토 숫자에 1을 더해서 적어주는 방식을 택했다.

[[9, 8, 7, 6, 5, 4],
 [8, 7, 6, 5, 4, 3],
 [7, 6, 5, 4, 3, 2],
 [6, 5, 4, 3, 2, 1]]

예시 1번에 대한 box 실행 결과이다.
이중리스트에 토마토의 상태와 함께 익는데 걸리는 시간을 적어줌으로써
일반적인 경우와 토마토가 전부익어있는 상태를 함께 처리할 수 있다.
이중리스트의 값들중 가장 큰 값 -1 이 정답값이 되는데,
예시 1번에 경우에서는 가장 큰 값 9 - 1 = 8이 정답이고
예시 5번과 같이 모든 토마토가 익어있는 상태의 입력의 경우에도 가장 큰 값은 1 - 1 = 0으로 정답을 구할 수 있다.

 

전부 익었는지 체크 & Max 값 구하기

def get_max_day():
    max_day = 0
    for b in box :
        max_day = max(max_day, max(b))
    return max_day-1

def is_all_riped():
    for b in box :
        for tomato in b:
            if tomato == 0:
                return False
    return True

while문 처리이후에 최종 정답을 위해서 먼저 box 내의 토마토가 전부 익었는지 체크해주는 것이 필요하고,
다 익었다면 max 값을 구해야한다.
두 태스크에 대한 함수이다.

if not is_all_riped():
    print(-1)
else :
    print(get_max_day())

두 함수를 이용함으로써 최종 정답을 구할 수 있다.

 

최종 답안

from collections import deque

def get_max_day():
    max_day = 0
    for b in box :
        max_day = max(max_day, max(b))
    return max_day-1

def is_all_riped():
    for b in box :
        for tomato in b:
            if tomato == 0:
                return False
    return True



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

M, N = map(int, input().split())
box = []
tomato_q = deque()

for i in range(N):
    line = list(map(int, input().split()))
    for j, l in enumerate(line) :
        if l == 1:
            tomato_q.append([i,j])
    box.append(line)

while len(tomato_q) > 0 :
    x, y = tomato_q.popleft()
    day = box[x][y]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0 :
            box[nx][ny] = day + 1
            tomato_q.append([nx, ny])

if not is_all_riped():
    print(-1)
else :
    print(get_max_day())