[python] 7576번 - 토마토

문제

파이썬 풀이

최소 날짜를 구하기 위해서 BFS를 사용하고, 탐색을 할 때마다 이전 탐색 지점 + 1을 값으로 저장해주어 날짜를 저장해준다.

즉 마지막에 탐색하는 칸에는 가장 큰 값이 들어 있고, 1부터 시작했기 때문에 max값 -1 이 모두 익은 날짜 이다.

 

탐색을 어떤 식으로 시작을 해야할지에 고민이 많았는데 이 문제에서의 포인트는 미리 모든 토마토를 탐색하여 이미 익어있는 토마토를 탐색 큐에 집어넣고 탐색을 시작하는 것이 포인트였다.

 

BFS 코드

def bfs() :

    while q :
        x, y = q.popleft()
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m :
                continue
            if matrix[nx][ny] == -1 :
                continue
            if matrix[nx][ny] == 0 :
                matrix[nx][ny] = matrix[x][y] + 1
                q.append((nx,ny))

 탐색 큐인 q에는 이미 익어있는 토마토들의 위치가 들어가 있는 상태이다.

nx, ny가 상자 범위를 넘어가면 continue, 이동한 nx, ny의 값이 -1이면 토마토가 들어있지 않은 칸이므로 이동할 수 없어 continue

즉 이동할 칸에 있는 토마토가 안익은 상태인 0일때만 이동하여, 해당 토마토가 익게되고 해당 값에는 이전 칸의 저장되어있는 값(날짜) + 1을 저장하고 큐에 집어 넣는다.

 

탐색 전

for i in range(n) :
    for j in range(m) :
        if matrix[i][j] == 1 :
            q.append((i,j))

탐색 전 모든 칸을 돌면서 익어있는 토마토의 위치를 큐에 집어넣는 과정이다.

탐색 후

result = 0

...

for l in matrix :
    if 0 in l :
    # 안익은 토마토(0)이 1개 이상이라도 있다면 모두 익지 못함
        result = -1

if result != -1 :
    result = max(map(max, matrix))-1

print(result)

탐색을 모두 마친 후 토마토가 들어있는 모든 칸을 다시 살펴봤을 때 안익은 토마토(0)가 1개 이상 있다면 모두 익지 못했으므로 -1을 출력하기 위해 result를 -1로 바꾼다.

result값이 -1로 할당이 되지 않았다면, 탐색이 끝난 matrix를에서 최댓값을 찾아 -1을 뺀 값을 result에 넣는다.

이미 처음을 1로 시작했기 때문에 -1을 빼준다.

전체 코드

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

dx=[-1,0,1,0]
dy=[0,1,0,-1]
m, n = map(int, input().rstrip().split())
matrix=[list(map(int, input().rstrip().split())) for _ in range(n)]
q = deque()
result = 0


def bfs() :

    while q :
        x, y = q.popleft()
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m :
                continue
            if matrix[nx][ny] == -1 :
                continue
            if matrix[nx][ny] == 0 :
                matrix[nx][ny] = matrix[x][y] + 1
                q.append((nx,ny))

for i in range(n) :
    for j in range(m) :
        if matrix[i][j] == 1 :
            q.append((i,j))
bfs()

for l in matrix :
    if 0 in l :
    # 안익은 토마토(0)이 1개 이상이라도 있다면 모두 익지 못함
        result = -1

if result != -1 :
    result = max(map(max, matrix))-1

print(result)