[백준] 7576 토마토(BFS) - Python

 

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

7576번: 토마토

- 문제 설명

M * N 의 토마토 창고가 입력으로 주어진다.

창고 속에는 각각 익지 않은 토마토(0 입력), 익은 토마토(1 입력), 토마토가 없는 빈칸(-1 입력)이 주어진다.

익은 토마토는 안익은 토마토에게 영향을 주어 하루가 지나면 익은 토마토에 인접한 덜익은 토마토는

다음날 익은 토마토가 된다.

창고 속 안익은 토마토가 모두 익을때까지 걸리는 날짜를 구해보자.

 

- 입출력 예시

너비 우선 탐색(BFS) 알고리즘을 사용해 풀어보았다.

deque 모듈을 사용하지 않고 front, rear인덱스를 사용하는 방식으로 풀었었는데

백준에서는 시간초과를 피하기 힘들어 모듈을 사용하였다.

 

- 코드

from collections import deque
import sys
input = sys.stdin.readline
# 토마토판 4방향 탐색
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# 토마토 판을 넘어가는지 검사
def is_valid(r, c):
    return 0 <= r < M and 0 <= c < N

def BFS():
    # 방문했는지 체크할 리스트
    visited = [[False] * N for _ in range(M)]
    q = deque()     # 큐 생성
    # 토마토판 순회
    for i in range(M):
        for j in range(N):
            # 익은 토마토의 위치를 q에 추가
            if tomato[i][j] == 1:
                q.append((i, j))
                visited[i][j] = 1   # 방문체크, 1이라 선언
            # 토마토가 없는 위치 체크
            elif tomato[i][j] == -1:
                visited[i][j] = -1  # 토마토가 없다고 체크해줌

    while q:
        r, c = q.popleft()     # 큐의 첫번째 원소를 반환
        # 현재 위치 r,c에서 4방향 탐색
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            # 유효한 인덱스, 비어있지 않음, 방문한적 없음
            if is_valid(nr, nc) and tomato[nr][nc] != -1 and not visited[nr][nc]:
                q.append((nr, nc))  # 큐에 넣기
                # 방문처리, 하루가 지났다고 생각하고 전 위치값 +1 저장
                visited[nr][nc] = visited[r][c] + 1

    day = 0
    # 방문체크한 리스트 순회
    for i in visited:
        if day < max(i):      # 가장 오래걸린 기간 갱신
            day = max(i)-1    # 첫날을 1에서 시작했으므로 -1
        if False in i:        # 방문리스트에 방문 안한 곳이 있다면
            return -1         # return -1
    return day

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

print(BFS())