[BOJ/백준] 7576번 토마토 | BFS | 파이썬

문제

 

풀이

from collections import deque

def bfs(queue, box):    
    global days 
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]  
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m: 
                if box[nx][ny] == 0:  
                    box[nx][ny] = box[x][y] + 1
                    queue.append((nx,ny))
                    days = box[x][y]
    for b in box:  
        if 0 in b:
            return -1
    return days

m, n = map(int, input().split())
box = [[0] * m for _ in range(n)]  

days = 0
queue = deque()
for i in range(n):
    box[i] = list(map(int, input().split()))
    for j in range(m):
        if box[i][j] == 1:
            queue.append((i,j))
print(bfs(queue, box))

# for i in range(n):
#     print(box[i])

 

토마토가 익는 최소 일수를 구해야 하기 때문에 BFS를 사용했다.

 

전역 변수 days를 사용해 날짜를 셌다.

 

토마토 문제에서는 지난 문제와 달리 익은 토마토, 즉 값이 1인 경우가 여러 개일 수 있다.

  - 엘리먼트 삽입/삭제에 있어 연산 속도가 리스트보다 빠른 deque를 사용했다.

  - 반복문 안에서 box 리스트 엘리먼트 값이 1인 경우 queue에 추가했다.

*deque(덱): 양방향 큐. 리스트의 경우 엘리먼트 삭제 시 원소를 한 칸씩 옮겨줘야 해서 시간 복잡도가 O(n)인 반면, deque은 O(1)의 시간 복잡도를 가진다.

 

반복문이 끝난 후에 bfs 함수를 실행시켰다.

  - queue에 값이 없을 때 까지 popleft()로 꺼낸다.

  - 반복문 안에서 상하좌우에 안 익은 토마토(값이 0인 경우)가 있는지 확인한다.

  - 안익은 토마토가 있으면 queue에 추가하고 현재 리스트 엘리먼트 값으로 days값을 변경한다.

  - box 리스트 내 안 익은 토마토가 있는지 확인하고 있으면 -1을 아니면 days를 반환한다.

 

---

 

7576번: 토마토