[BOJ - bfs] 7576번 : 토마토 ( python )

 

백준 7576번 : 토마토 문제 (골드1)

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

7576번: 토마토

 

 

 

문제 요약

- m * n (가로*세로) 짜리 토마토 보관 창고가 있다. 

- 여기에 토마토를 넣어주는데 토마토는 다음과 같이 표기한다.

> 안익은 토마토 : 0

> 익은 토마토 : 1

> 토마토가 없음 : -1

 

- 안익은 토마토는 인접한 곳에 위치한 익은 토마토에 영향을 받아 익는다. (앞/뒤/오른쪽/왼쪽)

 

요구사항

- 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 최소일수를 출력

- 만약 익지 않는 토마토가 있으면 -1 출력

 

 

 

나는 최소 일수를 출력해야 한다는 말에 bfs를 이용해서 풀었다. (코테 시작한지 얼마 안돼서 구분 기준이 명확하지 않음)

 

 

코드 설명

1) 익은 토마토가 한개 이상이므로 익은토마토를 판별 후 큐에 먼저 넣어주었다. 

 

2) bfs 함수에서 4방향 확인 후에

이동하려고 하는 곳이 box 안이고, 그 위치에 안익은 토마토가 있을 때

box[xx][yy] = box[x][y] +1 를 써주었는데

>> 맨 처음에 box[x][y]는 1로 시작(익은 토마토의 위치부터 탐색)

이동할 떄마다 1씩 증가시켜서 어떤 위치에 도달하기까지 숫자를 저장해주는 것이다.

 

>>>> 맨처음에 익은 토마토가 1로 시작해서 다음 토마토가 익으면 map[xx][yy] == 2가 되는데 이때 걸린 일수는 1이다.

>>>> 즉 map에 저장되는 값들은 위치에 도달하기까지(토마토가 익는데) 걸린 일수 +1

>>>> 때문에 마지막에 1을 빼줘야한다. 

 

 

3) bfs() 수행 이후에 res= 0으로 초기화 하고,

box 전체를 살펴본다. 

bfs로 순회 이후엔 box에 각 위치의 토마토가 익을 때 까지 걸린 일수 +1가 저장되어 있다. 

 

box에 만약 0이 들어있으면, 순회가 끝났음에도 익지 않은 토마토가 존재하는 것 이므로 

-1 출력

 

0이 없으면 최대값을 가져와서 -1 을 해주고 출력해준다. 

 

 

최종코드

import sys
from collections import deque

input = sys.stdin.readline

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

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

q = deque()

for i in range(n):
	for j in range(m):
		if box[i][j] == 1:
			q.append((i,j))

def bfs():
	while q:
		x,y = q.popleft()
		
		for i in range(4):
			xx = x+dx[i]
			yy = y+dy[i]
			
			if (0<=xx<n) and (0<=yy<m) and box[xx][yy] == 0:
				# 토마토 = 1
				box[xx][yy] = box[x][y] +1
				q.append((xx,yy))
				
bfs()
res = 0
for tomatoes in box:
	if 0 in tomatoes:
		print(-1)
		exit(0)
	res = max(res, max(tomatoes))
print(res-1)

 

 

dfs bfs 좀더 열심히 풀어야지 !!