[BOJ]7576 - 토마토 (Python)

문제 

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

코드 

from collections import deque
import sys
input = lambda: sys.stdin.readline().strip()


def bfs():
    day = 0
    while queue:
        day += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    queue.append((nx, ny))

    for i in graph:
        for tomato in i:
            if tomato == 0:
                return -1

    return day - 1


m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
answer = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

print(bfs())

 

풀이 

문제를 보고 깊이를 탐색할 필요는 없으니 BFS로 풀어야겠다는 생각이 들어 바로 풀어보았다

하지만 날짜를 세는 부분이 어려워서 다른 사람의 풀이를 참고했다 

queue에 원소가 있을 때 돌면서 탐색을 하고 day를 하나씩 늘려준다 

탐색이 다 끝난 뒤에는 행렬에 0이 남아있으면 -1을 출력하고, 없으면 day-1을 출력한다 

여기서 1을 빼는 이유는 우리가 하루를 더하면서 반복문을 시작했기 때문이다 

 

배운점! 

✅ 난 항상 행렬/배열을 초기화 하고 반복문으로 입력을 받았었는데, 이 문제처럼 행렬 전체를 입력받을 경우 초기화를 할 때 입력받으면 된다 

graph = [list(map(int, input().split())) for _ in range(n)]