[백준] 7576본 토마토 파이썬 python

문제

처음 이 문제를 접했을 때 bfs인가 생각은 했지만 구현하기가 어려워
매일매일 1인 좌표의 상하좌우를 변경해주면서 날짜를 세는 방식으로 코드를 짰다.

초기코드

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


tomatos = [list(map(int, input().split())) for _ in range(n)]
ans = 0
#해당 날짜에 익은 토마토의 상하좌우를 익게 하는 함수
def day1():
    global ans
    visited = [[0] * m for _ in range(n)]
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    for i in range(n):
        for j in range(m):
            #이 날짜에 익은 토마토는 제외 원래 익어있던 토마토의 상하좌우만 방문
            if tomatos[i][j] == 1 and visited[i][j] == 0:
                visited[i][j] = 1
                for k in range(4):
                    nx = dx[k] + i
                    ny = dy[k] + j
                    #범위안에 있는 좌표이며 익지않은 토마토여야함
                    if 0<= nx <n and 0<= ny <m and tomatos[nx][ny] == 0:
                        tomatos[nx][ny] = 1
                        visited [nx][ny] = 1
    ans += 1
    return tomatos
before = 0
while(True):
    # 모두 익었다면 종료
    zero_cnt = 0 
    for i in range(n):
        zero_cnt += tomatos[i].count(0)
    if zero_cnt == 0:
        print(ans)
        break
    ##
    #하루가 더 지나도 0의개수가 동일하다면 익을수가 없는 상황이므로 -1출력
    if zero_cnt == before:
        print(-1)
        break
    day1()


    brfore = 0 
    for i in range(n):
        before += tomatos[i].count(0)

    before = zero_cnt

테스트케이스는 전부 출력되지만 시간초과가 발생하였다.

그래서 구글링을 해본 결과 bfs를 사용하는데 살짝 응용해주어서 문제를 해결해주면 된다는 것을 알게 되었다.

단순히 bfs만 돌리는 것이 아닌 첫번째 시작할 때 1로 주어진 좌표를 큐에 모두 append를 해준 후에 while문을 실행해야하고,

tomatoes[nx][ny] = tomatoes[x][y] + 1

이렇게 해주어서 각 좌표별 익기까지의 걸린 날짜를 기록해준 후 max 값을 구해주는 방식으로 해주면 된다.

이 부분은 bfs를 실행하면서 bfs의 그리드 수준에 대해 기록해주는 것으로 보면 된다 dp와 유사하게 보이지만 살짝 다르다

정답코드

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


tomatos = [list(map(int, input().split())) for _ in range(n)]
ans = 0


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


def bfs():
    global ans
    visited = [[0] * m for _ in range(n)]
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    while(q):
        x,y = q.popleft()
        for k in range(4):
            nx = dx[k] + x
            ny = dy[k] + y
            #범위안에 있는 좌표이며 익지않은 토마토여야함
            if 0<= nx <n and 0<= ny <m and tomatos[nx][ny] == 0:
                tomatos[nx][ny] = tomatos[x][y] + 1
                visited [nx][ny] = 1
                q.append((nx,ny))


bfs()

ans = 0
for i in range(n):
    for j in range(m):
        #bfs함수 실행 후에 안익은 토마토가 있다면 -1 출력 
        if tomatos[i][j] == 0 :
            print(-1)
            exit(0)
    ans = max(ans,max(tomatos[i]))


print(ans-1)