https://www.acmicpc.net/problem/7576
7576번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토www.acmicpc.net
거의 처음으로풀어본 BFS문제라 좀 시행착오를 많이 겪었다.
하다보면 나아지겠지
먼져, 주어진 배열을 돌면서 stack에 원소가 1인 자릿값들을 넣는것부터 시작한다.
토마토는 총 4방향으로 익기 시작하므로, moves=[[0,1],[0,-1],[1,0],[-1,0]] 를 선언해준다.
이후 각각 BFS를 돌면서, 만일 원소가 -1이거나 1인 경우(이미 익은 경우) 를 제외하고, 계속 확장시킨다.
더히상 갈데가 없을때까지 bfs를 돈 후, 다시 배열을 돌면서 0이 하나라도 있으면 -1을 리턴하면 된다.
여기서 bfs의 level을 어떻게 구현해야하는지 몰라서 헤멨는데, 백준을 뒤져보다 좋은 방법을 발견했다.
스택에 i,j값만 넣지 말고, 레벨을 같이 넣는 것이다.
가장 처음엔 0단계이므로, i,j,0을 넣는다.
이후 스택 각각의 원소들이 확장할때마다, level+1을 해 준다.
다시 돌아가서, 배열에 0이 하나도없으면 마지막level을 출력한다.
##코드##
import sysfrom collections import dequeinput=sys.stdin.readline
def bfs(m,n,box,forbfs): moves=[[0,1],[0,-1],[1,0],[-1,0]] l=0
while forbfs: i,j,l=forbfs.popleft()
for move in moves: tmp_i=i+move[0] tmp_j=j+move[1]
if 0<=tmp_i<n and 0<=tmp_j<m:
if box[tmp_i][tmp_j]==0:
forbfs.append([tmp_i,tmp_j,l+1])
box[tmp_i][tmp_j]=1 for aa in range(n):
for bb in range(m): if box[aa][bb]==0:
return-1 return l m,n=map(int,input().split())
box=[[*map(int,input().strip().split())]for _ in range(n)]forbfs=deque()
for i in range(n): for j in range(m): if box[i][j]==1:
forbfs.append([i,j,0])
print(bfs(m,n,box,forbfs))