[Python Algorithm] 토마토 BOJ #7576

문제

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

7576번: 토마토

 

내 문제 풀이

import sys, copy
m, n = map(int, sys.stdin.readline().split())
storage = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
queue = []
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
countCheck = copy.deepcopy(storage)
result = 0
zero = False

def bfs(count):
    index = 0
    while len(queue) > index:
        x, y, n_count = queue[index][0], queue[index][1], queue[index][2]
        index += 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m: continue
            if storage[nx][ny] == 0:
                storage[nx][ny] = 1
                countCheck[nx][ny] = n_count+1
                queue.append((nx, ny, n_count+1))

for i in range(n):
    for j in range(m):
        if storage[i][j] == 1:
            queue.append((i, j, 0))
        if storage[i][j] == 0:
            zero = True

if zero == False:
    print(0)
else:
    bfs(0)
    for i in range(n):
        if 0 in storage[i]:
            result = -1
            break
        result = max(result, max(countCheck[i]))

    print(result)

👉 BFS 문제로, 모든 익은 토마토들을 시작점으로 동시에 탐색을 진행해주는게 포인트!

• 주어진 창고의 모든 자리를 돌며 1이 있는 자리는 queue에 넣어주었고,
  익은 토마토들의 자리가 저장된 queue를 가지고 bfs 함수를 돌렸다.
• bfs 함수로는 queue에 저장된 토마토들의 상하좌우를 탐색하고,
  0을 발견하면 해당 토마토를 1로 바꾸어주었다. 그리고 한 번 토마토를 익힐 때마다
  count을 증가시켜주어서 countCheck 리스트에 누적하여 기록했다.
  그리고 이 countCheck의 최댓값을 구하여 결과로 출력하게 했다.

(저번에 swift로 풀었던 풀이👇와 유사한 것 같아서 자세한 설명은 생략하겠다.

https://seolhee2750.tistory.com/126)

 

 

💡 피드백

• 전형적인 bfs 문제라 쉽게 풀 수 있었다.