LeetCode : 200. Number of Islands

문제

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

 

풀이

1. numIsLands 함수에서는 grid의 모든 값을 돌면서, 해당 위치가 land를 의미하는 ‘1’이 라면 아래 search 함수를 실행함
2. search는 재귀함수
   1. 인덱스가 범위 밖이거나 값이 1이 아닌 경우는 return을 함
   2. 그 외에는 해당 인덱스에 임의의 값(2)를 넣어주고, 인덱스를 중심으로 상하좌우로 search 함수를 호출함
3. 이미 방문한 위치에 1이 아닌 임의의 값을 넣어 뒀으므로, 중복된 섬 찾기는 피할 수 있음