Number of Islands

지도는 길이가 같은 행들의 목록으로 주어집니다. 각 문자는 육지 칸인 1 또는 물 칸인 0입니다. 두 육지 칸은 하나가 다른 하나의 바로 위, 아래, 왼쪽 또는 오른쪽에 있을 때 같은 섬에 속합니다. 모서리만 맞닿은 칸은 연결되지 않습니다.

다음 지도를 살펴보세요: ["11000", "11000", "00100", "00011"]

• 왼쪽 위의 육지 칸 네 개가 하나의 섬을 이룹니다.
• 가운데 행의 한 칸은 첫 번째 섬과 모서리만 맞닿아 있으므로 두 번째 섬입니다.
• 오른쪽 아래의 두 칸은 세 번째 섬을 이룹니다.

따라서 지도에는 섬이 3개 있습니다.

지도는 실제로 그래프입니다. 각 육지 칸은 노드이고, 변은 변을 공유하는 두 육지 칸을 연결합니다. 섬의 개수를 세는 것은 그래프에서 연결된 구성 요소의 개수를 세는 것입니다. 아직 방문하지 않은 육지 칸을 찾을 때마다 새로운 섬을 발견한 것이므로, 다음으로 넘어가기 전에 그 섬 전체를 탐색합니다.

grid를 입력받는 numIslands라는 함수를 작성하세요. grid는 1(육지)과 0(물)로 이루어진 문자열 목록이며, 함수는 섬의 개수를 반환해야 합니다. 섬은 위, 아래, 왼쪽 또는 오른쪽으로 연결된 육지 칸들의 그룹입니다.

예를 들어, ["01110", "01000", "00011", "11001"]은 3을 반환합니다. 위쪽 행들에 있는 모양, 오른쪽의 그룹, 그리고 왼쪽 아래 모서리의 한 쌍이 각각 섬입니다.

제약 조건: 1 <= 행의 수, 열의 수 <= 150. 모든 행의 길이는 같습니다.