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

문제 설명

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

7576번: 토마토

---

문제 풀이

전형적인 BFS 문제

시작점이 여러 개인 BFS 문제를 처음 풀어봐서 풀다가 당황 ,,,,

BFS 자체가 너비 우선으로 탐색하기 때문에 1일차, 2일차 이렇게 순서대로 큐에 들어간다

처음 시작점을 찾은 후 큐에 넣은 다음 BFS를 수행하면 된다 ! 

 

다 풀고 나서 코드 리뷰를 해본 결과

bfs 함수 안에서 큐를 다 돌고 나서 안 익은 토마토가 있을 때(값이 0일 때) return으로 처리해주면

zero 변수를 만들어 줄 필요 없이 바로 리턴 값을 print 하면 된다....

이렇게 바로 return을 해주면 bfs() 밑에 있는 부분들을 안 써도 됨

 

from collections import deque

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

    

m, n = list(map(int, input().split()))
tomato = [list(map(int, input().split())) for _ in range(n)]

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

for i, tm in enumerate(tomato):
    for j, t in enumerate(tm):
        if t == 1:
            queue.append((i, j))

bfs()

# 코드 리뷰
# rst = 0
# for t in tomato:
#     if 0 in t:
#         return -1
#     rst = max(max(t), rst)
# return rst - 1

zero = False
result = 0
for tm in tomato:
    if 0 in tm:
        zero = True
        break
    result = max(result, max(tm))

if zero:
    result = -1
else:
    result -= 1

print(result)