[백준] 7576번 토마토 - 파이썬(Python)

시간 제한	메모리 제한
1 초	256 MB

문제 (링크)

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

7576번: 토마토

 

나의 풀이

from collections import deque

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

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

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, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
        	if graph[nx][ny] == 0:
            	q.append((ny, nx))
                graph[nx][ny] = graph[x][y] + 1

max_day = -1

for i in range(n):
	# bfs 후에도 익지 않은 토마토가 있다면
	if 0 in graph[i]:
    	max_day = -1
	
    # graph[i]의 최대일 수와 지금까지 기록된 최대일 수 비교
    max_day = max(max_day, max(graph[i]))
        break
        
# 아직 익지 않은 토마토가 있을 경우는 -1 출력        
if max_day == -1:
	print(max_day)

# bfs 시작을 1로 잡았으므로, 실제로 익는 시간은 최댓값 - 1
else:
	print(max_day -1)

 

접근 방법 및 코드 설명

처음엔 엄두도 못냈던 문제지만, bfs에 조금 익숙해지고 나니 생각보다 간단한 문제였다.

 

입력값으로 받아온 그래프 중에서 초기 토마토의 위치(값이 1인 경우)를 bfs를 위한 큐에 미리 넣어놓고, 해당 값들에서 시작하는 bfs를 진행해주면 된다.

 

이 문제 역시 방문여부를 visited 같은 변수를 따로 만들어 저장할게 아니라, 오로지 0일때만 bfs를 실행하도록 코드를 작성하여 이미 방문한 위치는 방문하지 않도록 지정해주었다.

 

처음에 도저히 방법을 몰랐던 최소 날짜를 구하는 방법 또한 최단 거리를 구한다는 개념으로써 graph[nx][ny]의 위치에 이전 값에 1을 더한 값을 저장해줌으로써 별 어려움 없이 날짜를 구할 수 있었다.