[백준 7569] 토마토

🍎 [백준 7569] 토마토

문제 링크

⚾ 코드

    from collections import deque

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

    for i in range(H):
        for _ in range(N):
            grid[i].append(list(map(int, input().split())))
    # grid[i] = i층
    # grid[i][x][y] = i층의 x, y좌표

    q = deque()

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


    def check_range(h, x, y):
        if x >= 0 and x < N and y >= 0 and y < M and h >= 0 and h < H:
            return True
        return False


    def bfs():
        while q:
            h, x, y = q.popleft()
            # 4 방향 살펴보기
            for i in range(6):
                nh = h+dh[i]
                nx = x+dx[i]
                ny = y+dy[i]

                # 0이 아닌 경우는 토마토가 없거나(-1), 이미 방문한 경우임
                if check_range(nh, nx, ny) and grid[nh][nx][ny] == 0:
                    grid[nh][nx][ny] = grid[h][x][y]+1
                    q.append([nh, nx, ny])


    # 토마토의 위치 append
    for h in range(H):
        for i in range(N):
            for j in range(M):
                if grid[h][i][j] == 1:
                    q.append([h, i, j])
    bfs()


    answer = 0
    mark = True

    for i in range(H):
        for j in range(N):
            # 0이 grid 안에 존재할 경우는 -1 출력
            if 0 in grid[i][j]:
                mark = False
                break
            answer = max(answer, max(grid[i][j]))

    if mark:
        # 0이 gird 안에 존재하지 않을 경우
        # 첫 날도 날짜에 넣었으므로 -1 해주기
        print(answer-1)
    else:
        print(-1)

🔔 해결과정 & 깨달은 점

• BFS의 아이디어를 활용해 풀었다.
• 바로 전에 푼 토마토 문제의 3D 버전이라서 위 아래 탐색하는 코드만 조금 추가해주었다.