[백준][파이썬] 7576번 토마토

백준 온라인저지 7576번 토마토

문제풀러 바로가기👇👇👇👇👇👇

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

7576번: 토마토

 

 

 

 

 

문제풀이

---

1. 바이러스같이 퍼져가는 구조이므로 bfs를 사용해야한다.

 

2. 퍼져나가면서 1씩 증가시켜 기록하면 최대값을 통해 모두 익을 때까지의 최소 날짜를 알 수 있다.

 

3. dx, dy 배열을 이용해 사방에 있는 토마토들을 탐색하자.

 

4. 만약 bfs를 사용해서 탐색했는데도 0이 남아있다면 -1에 의해 가로막혀 있는 것이므로 토마토가 모두 익지 못하는 상황이다.

 

 

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

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

m, n = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# 각각 퍼져나갈 수 있도록 큐에 익은 토마토 삽입
q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i, j))
            
# bfs
while q:
    x, y = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue

        if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y] + 1
            q.append((nx, ny))

result = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(-1)
            exit()
    result = max(result, max(graph[i]))
print(result-1)

 

 

Python3와 PyPy3의 차이

유형	메모리	시간	언어	코드 길이
수정본 + 언어 바꿈	170564KB	432 ms	PyPy3	798 B
수정본(sys.stdin.readline 사용)	97864KB	2704ms	Python3	798 B
초안	97924KB	2808ms	Python3	768 B

두 언어의 시간 차이가 굉장히 많이 발생했다.