해커를 꿈꾸는 개발자

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

www.acmicpc.net/problem/7576

문제 풀이 

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

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

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

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

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

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

전체 코드

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)