[python] 7576. 토마토

문제 출처

7576. 토마토

 

풀이

주어진 배열에서 익은 토마토의 위치를 찾고, 그 위치부터 배열 전체의 가능한 부분을 BFS 탐색 하는 문제이다. 이 문제에서 최악의 경우 배열의 크기는 10^6으로 단순히 리스트 형식의 자료구조로 BFS 탐색을 하게되면 시간초과가 발생한다. 합격 코드는 단순 리스트구조와 heapq, deque로 해결한 풀이를 모두 작성했다.

 

단순 리스트(시간 초과)

 

M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

q = []
for y in range(N):
    for x in range(M):
        if arr[y][x] == 1:
            q.append((0, y, x))
            arr[y][x] = -1

while q:
    t, y, x = q.pop(0)
    for dx, dy in (0, -1), (1, 0), (0, 1), (-1, 0):
        nt, ny, nx = t+1, y+dy, x+dx
        if ny < 0 or ny >= N or nx < 0 or nx >= M:
            continue
        if arr[ny][nx] == -1:
            continue
        q.append((nt, ny, nx))
        arr[ny][nx] = -1

def left():
    for y in range(N):
        for x in range(M):
            if arr[y][x] == 0:
                return -1
    return t

print(left())

 

 

heapq(3440ms)

 

from collections import deque

M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

q = []
for y in range(N):
    for x in range(M):
        if arr[y][x] == 1:
            heappush(q, (0, y, x))
            arr[y][x] = -1

while q:
    t, y, x = heappop(q)
    for dx, dy in (0, -1), (1, 0), (0, 1), (-1, 0):
        nt, ny, nx = t+1, y+dy, x+dx
        if nx < 0 or nx >= M or ny < 0 or ny >= N:
            continue
        if arr[ny][nx] == -1:
            continue
        heappush(q, (nt, ny, nx))
        arr[ny][nx] = -1

def left():
    for y in range(N):
        for x in range(M):
            if arr[y][x] == 0:
                return -1
    return t

print(left())

 

 

deque(764ms)

 

from heapq import heappop, heappush

M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

q = deque()
for y in range(N):
    for x in range(M):
        if arr[y][x] == 1:
            q.append((0, y, x))

while q:
    t, y, x = q.popleft()
    for dx, dy in (0, -1), (1, 0), (0, 1), (-1, 0):
        nt, ny, nx = t+1, y+dy, x+dx
        if  ny < 0 or ny >= N or nx < 0 or nx >= M:
            continue
        if arr[ny][nx] == -1:
            continue
        q.append((nt, ny, nx))
        arr[ny][nx] = -1

def left():
    for y in range(N):
        for x in range(M):
            if arr[y][x] == 0:
                return -1
    return t

print(left())