[백준 7576] 토마토

🍎 [백준 7576] 토마토

문제 링크

⚾ 코드

    from collections import deque

    M, N = map(int, input().split())
    grid = []

    for _ in range(N):
        grid.append(list(map(int, input().split())))

    q = deque()

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


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


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

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


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

    answer = 0
    mark = True

    for i in range(N):
        # 0이 grid 안에 존재할 경우는 -1 출력
        if 0 in grid[i]:
            mark = False
            break
        answer = max(answer, max(grid[i]))
    if mark:
        # 0이 gird 안에 존재하지 않을 경우
        # 첫 날도 날짜에 넣었으므로 -1 해주기
        print(answer-1)
    else:
        print(-1)

 

🔔 해결과정 & 깨달은 점

• BFS의 아이디어를 활용해 풀었다.
• 다음 날부터 세는데, 첫째 날부터 날짜에 포함했으므로 결과를 출력할 때는 -1을 해주어야 한다.