[Python] 백준 7569 토마토

🧑‍💻 [Python] 백준 7569 토마토

Gold 5 - BFS

무조건 BFS로 풀어야 하는 문제이다

시작점이 하나가 아닐 수 있다

• 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다

BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다

마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다

7576과 같은 문제이지만, 높이가 추가가 되었다

• 3중 포문을 쓰되, 3중 리스트 사용법을 익혀야 한

문제풀이

• bfs 식
  • 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용
• 첫 for문
  • queue에다가 시작 점들을 넣는다
  • 시작점이 하나일 때에는 for문을 돌릴 필요가 없지만, 이 문제에서는 시작점이 1개 이상이 주어질 수 있다
• 두번째 for문
  • 결과값을 탐색한다
  • bfs를 다 돌고나면, box에 몇 일이 지났는지, 숫자들이 표기되어 있다
  • 각 열을 돌며, 열에서 제일 큰 숫자를 answer에 저장을 한다
  • 단, 0이 하나라도 발견이 된다면, flag는 False로 바꾼다
    • 이 뜻은, 모든 토마토가 다 익지 못 했다는 것이다
    • 즉 -1을 출력해야 한다

코드

from collections import deque

def bfs(queue):

    while queue:
        current_h, current_r, current_c = queue.popleft()

        for i in range(6):
            sh, sr, sc = current_h + dh[i], current_r + dr[i], current_c + dc[i]

            if 0 <= sr < N and 0 <= sc < M and 0 <= sh < H:
                if box[sh][sr][sc] == 0 and box[sh][sr][sc] != -1:
                    box[sh][sr][sc] = box[current_h][current_r][current_c] + 1
                    queue.append((sh, sr, sc))

M, N, H = map(int, input().split())

box = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]

queue = deque([])

# 북서동남, 위 아래
dh, dr, dc= [0, 0, 0, 0, -1, 1], [-1, 0, 0, 1, 0, 0], [0, -1, 1, 0, 0, 0]

answer = 0

# queue에다 시작 점들 넣기
for h in range(H):
    for r in range(N):
        for c in range(M):
            if box[h][r][c] == 1:
                queue.append((h, r, c))

bfs(queue)

flag = True
for h in range(H):
    if flag == False:
        break
    for r in range(N):
        if flag == False:
            break
        for c in range(M):
            if box[h][r][c] == 0:
                flag = False
                break

        answer = max(answer, max(box[h][r]))

if flag == False:
    print(-1)
else:
    print(answer -1)