합병 후보 칸 세기

문제

0과 1로 이루어진 2차원 격자가 주어집니다. 1은 땅, 0은 바다이며, 상하좌우로 연결된 땅들은 같은 섬을 이룹니다.

어느 도시 계획팀이 바다(0) 한 칸을 매립해 땅(1)으로 바꾸려 합니다. 어떤 0칸을 매립했을 때, 그 칸을 매개로 서로 다른 섬이 2개 이상 하나로 합쳐진다면 그 칸을 "합병 후보 칸" 이라고 부릅니다.

매립 가능한 "합병 후보 칸" 의 개수를 반환하세요. (실제로 매립하지는 않습니다. 각 0칸을 독립적으로 판단합니다.)

예시

grid = [
  [1,0,1]
] → 1
(가운데 0칸이 좌·우 두 섬을 잇는다 → 합병 후보 1개)
 
grid = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
] → 0
(둘레가 전부 연결된 섬 1개뿐. 가운데 0칸을 매립해도
 닿는 섬은 한 종류라 합병이 일어나지 않음 → 0개)

제약 조건

• 1 ≤ grid.length, grid[0].length ≤ 50
• grid[i][j]는 0 또는 1

시간 복잡도 목표: O(N × M)

공간 복잡도 목표: O(N × M)