[백준/Python] 7576번(BFS)_토마토

📌문제 유형

BFS (골드 Lv.5)

 

📌문제

7576번: 토마토

 

📌나의 문제풀이

- maps 전체 순회하여 1인거 q에 저장

- while q에서 maps[nx][ny] == 0인거 maps[x][y] + 1하면서 늘려감

- 가장 큰 값 -1 이 답

from collections import deque

m,n = map(int, input().split())

maps = []
for _ in range(n):
    maps.append(list(map(int,input().split())))

# 익은 토마토 다수인 경우
q = deque([])
for x in range(n):
    for y in range(m):
        if maps[x][y] == 1:
            q.append((x,y))

while q:
    x_,y_ = q.popleft()
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    for i in range(4):
        nx = x_ + dx[i]
        ny = y_ + dy[i]
        if 0 <= nx <n and 0 <= ny < m:
            if maps[nx][ny] == 0:
                maps[nx][ny] = maps[x_][y_] + 1
                q.append((nx,ny))
    # print(maps)
ans = 0
max_ = 1
for j in range(n):
    for k in range(m):
        if maps[j][k] == 0:
            ans = -1
        else:
            if max_ < maps[j][k]:
                max_ = maps[j][k]

if ans == -1:
    print(-1)
else:
    print(max_-1)

 

📌 다른사람의 문제풀이

- 똑같은 풀이

[백준] 7576: 토마토 (파이썬 / 해설포함)

from collections import deque

m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
res = 0

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])

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

bfs()
for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res, max(i))
print(res - 1)

 

📌 리뷰

- 3차원 토마토 문제 풀다가 2차원 토마토 문제 푸니 바로 풀림....

- 3차원 토마토도 풀러 가보자..