[백준] 7576 - 토마토 (Python)

[백준] 7576 - 토마토

• https://www.acmicpc.net/problem/7576
• 알고리즘:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색

풀이1 - BFS (시간초과)

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

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

for i in range(N):
    for j in range(M):
        if arr[i][j]==1:
            queue.append((i,j)) #익은 토마토 위치 넣기

def bfs():
    while queue:
        x=queue[0][0]
        y=queue[0][1]
        queue.pop(0)

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<N and ny>=0 and ny<M:
                if arr[nx][ny]==0:
                    arr[nx][ny]=arr[x][y]+1
                    queue.append((nx,ny))

def result():
    answer = 0
    for num in arr:
        if 0 in num:
            answer = -1

    if answer == -1: #토마토가 모두 익지는 못하는 상황인 경우
        print(-1)
    else:
        print(max(map(max, arr)) - 1)

bfs()
result()

그동안 BFS 문제를 풀 때 큐(Queue)를 list를 이용하여 구현했었는데, 이번 문제는 풀고 나서 답은 맞았지만 시간초과가 일어나는 문제가 발생했다.

---

풀이2 - BFS (시간초과 해결)

from collections import deque

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

queue=deque() #deque
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(N):
    for j in range(M):
        if arr[i][j]==1:
            queue.append((i,j)) #익은 토마토 위치 넣기

def bfs():
    while queue:
        x=queue[0][0]
        y=queue[0][1]
        queue.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<N and ny>=0 and ny<M:
                if arr[nx][ny]==0: #아직 방문하지 않은 경우
                    arr[nx][ny]=arr[x][y]+1
                    queue.append((nx,ny))

def result():
    answer = 0
    for num in arr:
        if 0 in num:
            answer = -1

    if answer == -1: #토마토가 모두 익지는 못하는 상황인 경우
        print(-1)
    else:
        print(max(map(max, arr)) - 1)

bfs()
result()

BFS에서 큐(Queue)를 list 대신 deque로 구현한 결과 시간초과 문제를 해결할 수 있었다.

---

📌 BFS에서 큐(queue)는 collections.deque를 사용하는 것이 더 효율적

• list에서의 pop은 시간복잡도 O(n)
• deque에서의 pop은 시간복잡도 O(1)

• algorithms