[Python] 백준 #7576 토마토 시간단축 성공!!!!

www.acmicpc.net/problem/7576

7576번: 토마토

from collections import deque
import sys


def BFS():
    que = deque()

    # 토마토가 있는 모든 값들을 먼저 넣어주자!
    for a in range(n):
        for b in range(m):
            if List[a][b] == 1:
                que.append([a, b])

    while que:
        p = que.popleft()
        x = p[0]
        y = p[1]

        for k in range(4):
            xx = dx[k]
            yy = dy[k]

            if xx + x < 0 or xx + x >= n or yy + y < 0 or yy + y >= m:
                continue

            else:  # 범위를 넘어가지 않음
                if List[xx + x][yy + y] == 0:
                    que.append([xx + x, yy + y])
                    List[xx + x][yy + y] = List[x][y] + 1

    return List

m,n=map(int,sys.stdin.readline().rstrip().split())
List = []

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

for i in range(n):
    List.append(list(map(int, sys.stdin.readline().rstrip().split())))

BFS()

Max=0
check = 0

for i in range(n):
    for j in range(m):
        if List[i][j] == 0:
            check = -1  # 안 익은 부분이 있음
            break
        if Max < List[i][j]:
            Max = List[i][j]

if check == -1:
    print(-1)

else:
    if Max == 1:  # 처음부터 모두 익어있었다는 것
        print(0)
    else:
        print(Max-1)

BFS를 이용하여 하나씩 방문하면서 토마토 개수를 바꿔가며 카운트해줬다

주의 해야 할 점은 여기서 여러개의 익은 토마토가 있으면 그게 동시에 주변에 영향을 준다는 점을 고려해야한다

예를 들면 아래와 같은 반례..!!!!

6 5

0 0 1 0 0 0

0 0 0 0 0 0

1 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 0 0

 

29일전에 풀었던 문제인데, 시간을 절반 정도를 단축 시켜서 기분이 좋다.. 무야호 ~~~

 

29일전

 

무야호~