백준/ Gold 5 문제 , 백준 파이썬 7576 , 토마토 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 7576 , 토마토 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
한곳에서만 출발하면 안되고 표의 1이 해당하는 구역에서 모두 같이 퍼져야한다. 이 점이 가장 중요.

 

 

<문제 출처> 

 

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

7576번: 토마토

------------------------------------------------------------------------------------------------------------------------------

 

이 문제의 핵심은 처음만나는 1에서부터 시작하는게 아니고

 

모든 1이 있는 지역에서 똑같이 퍼져야한다.

 

그러므로 1을 만날때마다 check 함수를 호출 하는 것이아닌

 

전체에서 1의 위치를 모두 dq에 저장한 뒤에 호출 시킨다.

 

그래야 모든 1 부분에서 똑같이 퍼져나갈 수 있으며, 퍼질때마다 이전 자리 숫자에서 +1을 해나가면 된다.

 

 

이후 표에서 가장 큰 수를 추출해 내서 -1 한 값을 출력해주면 된다.

 

참고로 표에 0이 하나라도 존재한다면 -1을 출력한 뒤 프로그램을 종료시킨다.

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

from collections import deque

vertical=[0,1,-1,0]
parallel=[1,0,0,-1]
dq=deque()

M,N=map(int,input().split())
place=[]
for _ in range(N):
    place.append(list(map(int,input().split())))
    
def check():
    while dq:
        i,j = dq.popleft()
        for k in range(4):
            move_x=i+vertical[k]
            move_y=j+parallel[k]
            if 0<=move_x<N and 0<=move_y<M:
                if place[move_x][move_y]==0:
                    dq.append([move_x,move_y])
                    place[move_x][move_y]=place[i][j]+1

for i in range(N):
    for j in range(M):
        if place[i][j]==1:
            dq.append([i,j])

check()

answer=0
boo=True
for i in range(N):
    for j in place[i]:
        if j>answer:
            answer=j
        if j==0:
            print(-1)
            exit(0)

print(answer-1)