[python] 7576: 토마토 시간초과 해결

7576: 토마토

생각의 전환

1. 그림문제와 같은 일반적인 BFS 문제에서 모든 곳을 시작점으로 두기 위해 2중 for문을 사용한다. 하지만 여기서도 같은 방식을 사용하면 시간초과가 난다. 이를 해결하기 위해 시작점을 queue에 미리 넣어두고 돌아야 한다. "어차피 BFS 도는 건 똑같은데 무슨 차이지?🤔" 싶을 것이다. 그림과 같이 물방울이 널리 퍼져보이는 모양에서는 2중 for문을 사용하고, 지금과 같이 시작점이 서로 멀리 떨어져 있을 때는 시작점을 미리 넣어두고 시작하면 시간초과를 막을 수 있다. 일종의 풀이법이다.
2. sum()을 사용하지 않는 것이다. sum(2차원 배열, [])을 사용하면 2차원 배열을 1차원 배열로 만들 수 있다. 문제는 범위가 커졌을 때 속도가 느리다는 것이다. sum과 2차원 배열을 각각 사용해서 max값을 찾을 때 소요되는 시간을 비교해봤다. 배열의 크기가 100일 때까지는 거의 차이가 없지만 더 커질 때는 속도 차이가 점점 커졌다. 토마토에서는 범위가 최대 1,000이라 시간초과가 났다.

import time
import random
start = time.time()

boardSize = 500
board = [[random.randint(-1, 1) for y in range(boardSize)]
         for _ in range(boardSize)]
# (1) sum
max(sum(board, []))

# (2) 2중 for
maxValue = 0
for x in range(boardSize):
    for y in range(boardSize):
        maxValue = max(maxValue, board[x][y])

print("time :", time.time() - start)

코드 설명

1. BFS 전: 값 입력받고 함수 실행
2. while 전: 시작점을 redTomatos에 넣는다. (문법상으로는 es를 붙어야 한다.)
3. while: 익은 토마토가 있을 때, 주위에 익지 않은 토마토가 있다면 빨간 토마토로 만든다.
4. 마지막 for: box를 확인하여 익지 않은 토마토가 하나라도 있다면 -1을 리턴한다. 이게 아니라면 걸린 시간을 출력한다.

코드

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

dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def BFS() -> int:
    redTomatos = deque()
    for startX in range(boxHight):
        for startY in range(boxWidth):
            if box[startX][startY] == 1:
                redTomatos.append({"redX": startX, "redY": startY})
                vis[startX][startY] = 1

    while redTomatos:
        cur = redTomatos.popleft()
        for mx, my in dir:
            nx = mx + cur["redX"]
            ny = my + cur["redY"]

            if nx < 0 or ny < 0 or nx > boxHight-1 or ny > boxWidth-1:
                continue
            if box[nx][ny] != 0 or vis[nx][ny] != 0:
                continue
            box[nx][ny] = 1
            vis[nx][ny] = vis[cur["redX"]][cur["redY"]]+1
            redTomatos.append({"redX": nx, "redY": ny})

    time = 0
    for x in range(boxHight):
        for y in range(boxWidth):
            if box[x][y] == 0:
                return -1
            time = max(time, vis[x][y])

    return time-1


boxWidth, boxHight = map(int, input().rsplit())
box = list(list(map(int, input().rsplit())) for _ in range(boxHight))
vis = [[0 for _ in range(boxWidth)]for _ in range(boxHight)]
print(BFS())

참고 링크

바킹독