Intro
Solution
- 방향을 지정한 리스트를 미리 선언하고, 입력받은 토마토의 위치를 큐를 만들어 집어넣는다.
- 너비 우선 탐색을 한다.
- 익지 않은 토마토를 토마토를 익힐 때마다 1을 더하며 그래프를 갱신한다.
- 그래프에서 가장 큰 값이 토마토를 모두 익히는데 필요한 최소 날짜이다.
- 익지 않은 토마토 즉 그래프에 0이 있을 경우 -1을 출력한다.
Code
from collections import deque
import sys
input = sys.stdin.readline
def solve():
m, n = map(int, input().split())
farm = [[*map(int, input().split())] for _ in range(n)]
queue = deque()
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
answer = 0
for i in range(n):
for j in range(m):
if farm[i][j] == 1:
queue.append((i, j))
def bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dxy[i][0]
ny = y + dxy[i][1]
if 0 <= nx < n and 0 <= ny < m and farm[nx][ny] == 0:
farm[nx][ny] = farm[x][y] + 1
queue.append((nx, ny))
bfs()
for i in farm:
for j in i:
if j == 0:
print(-1)
exit()
answer = max(answer, max(i))
print(answer-1)
solve()
'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/C++] 13549번 숨바꼭질 3 (0) | 2022.08.19 |
---|---|
[백준/JAVA] 13907번 세금 (0) | 2022.08.19 |
[백준/Python] 4963번: 섬의 개수 (0) | 2022.08.14 |
[백준/Python] 4485번 녹색 옷 입은 애가 젤다지? (0) | 2022.08.14 |
[백준/python] 2606번 바이러스 (0) | 2022.08.14 |