[Python] 7576번 : 토마토

 

문제 3줄 요약

1. 0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈 칸

2. 익지 않은 토마토는 익은 토마토 옆(상하좌우)에서 하루 뒤에 익는다. ex [1 0] → 1 일 후 → [1 1]

3. 모든 토마토가 익을려면 몇 일이 걸릴까? 모두 익지 못하는 상황이라면 -1 출력

 

 

 

 

문제 자체는 BFS를 사용하면 크게 어렵지 않았다고 느꼈지만...

BFS를 재귀를 이용하여 구현하여 막상 제출하니

런타임에러(Recursion Error)가 발생하였고,

재귀를 반복문으로 고쳐주니 시간 초과가 발생하였다.. ㅠㅠ

 

탐색할 자료구조를 처음엔 큐가 아닌 리스트를 큐를 대신하여 값을 빼주고 넣고 하였는데,

여기서 List의 pop(0)가 얼마나 무시무시한 시간 복잡도 인지를 알고 있지 못했다..

 

C++의 vector::erase(), Java의 ArrayList.remove(), Python의 list.pop() 등으로 배열의 첫 번째 원소를 지울 시, 그 뒤에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨오게 되므로, 그 시간 역시 원소의 수에 비례하여 소요됩니다

 

큐로 리스트를 사용할 경우에는

deque를 사용하는 것이 훨씬 빠르다는 글을 찾았다.

 

 

https://codingpractices.tistory.com/entry/Python%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%99%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%8C%80%EC%8B%A0-%ED%81%90-%EB%8D%B0%ED%81%AC-deque-%EB%A5%BC-%EC%93%B8%EA%B9%8C

[Python]파이썬, 왜 리스트대신 큐/ 데크 deque 를 쓸까?

 

참고하여

리스트가 아닌 deque로 대체하여 구현했더니,

바로 통과!!

 

 

from sys import stdin
from collections import deque

class XY:
    def __init__(self,x,y):
        self.x = x
        self.y = y

# 익지 않은 토마토 -> 익은 토마토
def BFS(good_t, day):
    add_q = deque()

    while(True):
        # BFS의 탐색할 큐를 갱신
        if len(good_t) == 0:
            if len(add_q) != 0:
                good_t.extend(add_q)
                add_q.clear()
                day += 1
            else:
                break

        x = good_t[0].x
        y = good_t[0].y
        
        ## Up
        if x > 0:
            if box[x-1][y] == 0:
                box[x-1][y] = 1
                add_q.append(XY(x-1,y))
        ## Left
        if y > 0:
            if box[x][y-1] == 0:
                box[x][y-1] = 1
                add_q.append(XY(x,y-1))
        ## Down
        if x+1 < N:
            if box[x+1][y] == 0:
                box[x+1][y] = 1
                add_q.append(XY(x+1,y))
        ## Right
        if y+1 < M:
            if box[x][y+1] == 0:
                box[x][y+1] = 1
                add_q.append(XY(x,y+1))
        
        good_t.popleft()

    return day

if __name__ == "__main__":
    # M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수
    # 2 ≤ M,N ≤ 1,000
    M, N = map(int, stdin.readline().split())
    good_t = deque()
    box = []
    day = 0
    for x in range(N):
        # 토마토 정보
        # 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토가 들어있지 않은 칸
        box_list = []
        for y,tomato in enumerate(map(int, stdin.readline().split())):
            if tomato == 1:
                good_t.append(XY(x,y))
            box_list.append(tomato)
        box.append(box_list)
    # 익은 토마토가 없는 경우
    if len(good_t) == 0:
        print(-1)
    else:
        day = BFS(good_t, day)

        for idx, tomato_l in enumerate(box):
            # 모든 토마토가 익지 못할 경우
            if tomato_l.count(0) != 0:
                print(-1)
                break
            
            if idx == len(box)-1:
                print(day)

 

오늘 푼 문제 덕에

큐를 사용하는 BFS 일 때는,

List를 피해야한다는 것을 알 수 있었다!

 

List.pop(0) vs deque.popleft()

deque 압승!

 

끝.