파이썬 / BOJ 백준 알고리즘 / 7576번 토마토 - BFS

파이썬 / BOJ 백준 알고리즘 / 7576번 토마토 - BFS

 

www.acmicpc.net/problem/7576

7576번: 토마토

문제 풀이 

 7576번 토마토 문제는 BFS로 풀 수 있습니다. 

 

이 문제를 풀기 위한 핵심음 아래와 같습니다. 

 

1. BFS에서 list보다는 queue(deque)를 사용하는 것이 동작 시간이 훨씬 빠릅니다. 

2. 상자의 토마토들의 정보를 한줄 입력할 때마다 토마토가 있으면(값이 1이면), Queue에 넣습니다. 

3. BFS 동작을 할 때에 pop을 한 좌표의 값에 1 증가한 값을 push 해주는 좌표의 값에 넣어주고, 마지막에 pop되는 값을 반환합니다. 

4. BFS 동작을 모두 끝내고, 배열의 모든 값을 검사하면서 0이 있는지 검사합니다. 

 

예제2번의 BFS를 진행하고 나서의 배열 정보

 

전체 코드

import sys
from collections import deque

dcol = [0, 0, 1, -1]
drow = [1, -1, 0, 0]

def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h or row < 0: return False
	return True

def show():
	for i in range(h):
		for j in range(w):
			print(maps[i][j], end=" ")
		print()

def bfs() :
	max = 0
	while queue:
		srow, scol = queue.popleft()

		for i in range(4):
			nrow = srow + drow[i]
			ncol = scol + dcol[i]

			if isRange(nrow, ncol) == False:
				continue
			if maps[nrow][ncol] != 0:
				continue
			#show()

			maps[nrow][ncol] = maps[srow][scol] + 1
			if max < maps[nrow][ncol]:
				max =  maps[nrow][ncol]
			queue.append((nrow, ncol))

	return max - 1


queue = deque()
maps = []
w,h = map(int, sys.stdin.readline().split())

for i in range(h):
	line = []
	line = list(map(int, sys.stdin.readline().split()))
	maps.append(line)
	for j in range(w):
		#print(" i = ", i , " , j = ", j , ", maps = ", maps[i][j])
		if line[j] == 1:
			queue.append((i, j))
result = 0
result = bfs()
if result == -1:
	result = 0

for i in range(h):
	if 0 in maps[i]:
		result = -1
		break
print(result)