접근
문제 자체는 간단한 BFS 문제였으나, 날짜를 입력하는 새로운 리스트를 만들어서 계산했을 때 시간초과가 나와서 조금 헤메게 되었다.
BFS 연관문제 : 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)
처음에 토마토판을 처음부터 끝까지 탐색하면서 1, 즉 토마토가 있는 칸을 큐에 추가해주었다. 그리고 큐에서 한개씩 popleft 시키면서 해당 칸의 위, 아래, 왼쪽, 오른쪽이 0, 즉 익지않은 토마토일 경우 현재 칸의 숫자보다 1 큰 값을 입력해주게 된다.
마지막으로 전체를 한바퀴 탐색하면서 max값을 탐색하고, 여전히 익지 않은 0이 있을 경우 -1을 출력하도록 해주면 된다.
코드
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
q = deque([])
for i in range(m):
for j in range(n):
if tomato[i][j] == 1:
q.append([i, j])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while q:
now = q.popleft()
for i in range(4):
nx = now[0] + dx[i]
ny = now[1] + dy[i]
if 0 <= nx < m and 0 <= ny < n and tomato[nx][ny] == 0:
tomato[nx][ny] = tomato[now[0]][now[1]] + 1
q.append([nx, ny])
maximum = 0
all = True
for i in tomato:
for j in i:
if j > maximum:
maximum = j
if j == 0:
all = False
if all:
print(maximum - 1)
else:
print(-1)
더 생각해 볼 것?
...
코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!
반응형
'코딩 > 백준 (Python)' 카테고리의 다른 글
백준 1697번: 숨바꼭질 (Python) (0) | 2021.04.12 |
---|---|
백준 7569번: 토마토 (Python) (0) | 2021.04.11 |
백준 2178번: 미로 탐색 (Python) (0) | 2021.04.11 |
백준 2667번: 단지번호붙이기 (Python) (0) | 2021.04.11 |
백준 1260번: DFS와 BFS (Python) (0) | 2021.04.11 |
최근댓글