[BJ] 7576 - 토마토 (BFS 시작점이 여러개)

 

일단 상하좌우로 퍼져나가니 BFS로 풀수있다는걸 눈치를 챌 수 있다.

하지만 여지껏 풀었던 BFS문제와 다르게 시작점이 여러개일수있다 TK 3번을 보자.

 

이렇게 input이 들어오게 되는데.

-1이 있는곳을 제외하고 퍼지면서 1씩 증가해야하니

이런식으로 되어야 할것이다.

 

근데 출력에서 0 = 처음부터 모두 토마토가 익어있는거고, -1은 모두 익지 못하는 상황이고,

나머지는 토마토가 익을 수 있는 일 수를 출력하는 것 이다.

 

그러면 여기서 input을 보면 생각을 해 볼 수 있다.

그러면 상하좌우로 갈 수 있는 부분만 -1로 미리 표시를 해놓으면 되지 않을까?

이런식으로 말이다.

-1만 움직일 수 있도록 해놓고 만약 -1일이 모두 상하좌우로 이어져 있지 않아서 BFS를 하고나서도 -1이 남아있다면?

모두 익지 못하는 상황이 될 것이다.

 

그리고 움직일 수 없다면(-1이 없다면) 0이 나오게 되니까 움직일 수 없다 즉 처음부터 모두 익어있는 상태이다 그럼 0을 출력하면 된다.

 

이제 BFS를 돌려서 다음과 같이 Check에 값을 넣어보자

움직이고 최댓값을 뽑으면 6 즉 정답이 나온다.