일반적인 생각.

: n * m 의 모든 정점에서 1인 타겟 pos를 얻어서 bfs를 순회해서 0인 지점을 카운팅하기에는 시간복잡도가 굉장히 커진다.

• 타겟을 잡더라도 4방면으로 bfs를 시도해야 한다.
  : bfs 비용은 n X m 이기 때문에 최종적으로 n X m X n X m
  의 시간복잡도가 발생하기 때문에 일반적인 방법으로 접근하면 안된다.

생각해보기

• 아래의 그래프를 가지고 생각해보면, 0,0 인 지점의 1을 가지고 아래의 3개 0칸을 순회한다.

• 0,1인 지점의 1을 가지고 아래의 3개의 0칸을 순회한다.

• 1,2인 지점의 1을 가지고 왼쪽 3개의 0칸을 순회한다.
  => 하나의 지점을 가지고 0이 있는 동일한 지점을 계속 순회하기에는 비효율적이라는 생각이 들지 않는가?

아이디어

• 쉽게 생각해볼 수 있는 거는 0인 인접해 있는 구간을 하나의 그룹으로 만들어 놓고,
• 인접한 1인 친구들이 접근할 때 해당 그룹에 있는 cnt값을 누적하면 위의 문제를 풀 수 있다.
  : 이런식으로
  

주의할점

• 초록색 친구는 왼쪽과 위에 동일한 그룹인데, 중복해서 누적해야 할까????? 아니다! 이를 유념해서 작성하자.