[리트코드] 200. Number of Islands

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

var numIslands = function(grid) {
  const dx = [-1, 1, 0, 0]
  const dy = [0, 0, -1, 1]
	let numOfLand = 0
	const array = Array.from(Array(grid.length), () => new Array(grid[0].length).fill(false))
  const isValid = (row, col) => row >= 0 && row < grid.length && col >= 0 && col < grid[row].length;
    function dfs(x,y){
        for(let i = 0; i < dx.length; i++){
            let nx = x + dx[i]
			let ny = y + dy[i]
            if(isValid(nx,ny) && grid[nx][ny] === '1' && !array[nx][ny]){
                array[nx][ny] = true
                dfs(nx,ny)
			}
        }
    }
    
		for(let j = 0;j < grid.length; j++){
			for(let k = 0;k < grid[j].length; k++){
				if(grid[j][k] === '1' && array[j][k] === false){
					array[j][k] = true
                    numOfLand++
                    dfs(j,k)
				}
			}
		}

return numOfLand
};

이중 배열을 돌면서 '1'인 경우는 땅 '0'인 경우는 바다를 나타내고 섬의  갯수를 묻는 문제입니다.

배열을 돌면서 그 값이 1일 경우에는 메이제이션 배열의 값을 true로 변경해줌으로써 방문했다는 것을 표시합니다.

섬의 갯수를 하나 증가 시킨 후 dfs 탐색을 들어갑니다.

 

주어진 위치의 상하좌우를 돌면서 '1'인 경우 방문했다는 것을 표시하고 재귀함수를 통해 값을 전달해줍니다.

모든 dfs탐색이 종료가 되면 섬이  하나 만들어진것입니다.

 

그 다음 다시 이중 배열을 돌면서 방문한 적 없고 값이 '1'인 곳이  있다면 섬의 갯수를 증가 시키고 dfs탐색을 시작합니다.