[백준] 토마토 7576 (Python)

문제 링크

https://www.acmicpc.net/problem/7576

7576번: 토마토

나의 풀이

bfs를 이용해 풀었습니다.

1. 입력 값 중 익은 토마토들을 탐색해 tomatos배열에 저장합니다.
   • [x,y, 언제 익었는지] -> 처음부터 익은 토마들이기 때문에 처음에는 [x, y, 0]으로 저장합니다.
2. tomatos를 이용해 queue를 생성합니다.
3. bfs를 수행합니다.
   • bfs는 현재 위치에 있는 토마토가 익은 위치에서만 탐색을 진행하기 때문에 if문을 이용해 1인 경우에만 탐색을 진행합니다.
   • 현재 익은 토마토 근처에 안익은 토마토가 있다면 [nx, ny, 이전 토마토가 익은 날 + 1] 을 q에 추가하고, 현재 위치의 토마토는 익었다는 표시를 합니다.

Code

# https://www.acmicpc.net/problem/7576
# 토마토

from collections import deque

def bfs(q,maps):

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

    answer = 0
    while q:
        x, y, day = q.popleft()
        answer = day
        if maps[x][y] == 1:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < height and 0 <= ny < width:
                    if maps[nx][ny] == 0:
                        maps[nx][ny] = 1
                        q.append([nx,ny,day+1])

    return answer

width, height = map(int, input().split())

maps = []
tomatos = []

for _ in range(height):
    tmp = list(map(int,input().split()))
    maps.append(tmp)

for i in range(height):
    for j in range(width):
        if maps[i][j] == 1:
            tomatos.append([i,j,0])
q = deque(tomatos)
answer = bfs(q,maps)

is_all = 1

for i in maps:
    if 0 in i:
        is_all = 0
        break
if is_all:
    print(answer)
else: print(-1)

Git

https://github.com/youngh0/Algorithm/blob/master/DFS%2CBFS/boj_7576.py