[leetcode 200] Number of Islands

200. Number of Islands

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

해결 과정

1을 만나면, 섬 개수를 ++을 하고 dfs (깊이우선탐색) 한다.

왼쪽/오른쪽/아래/위 샅샅이 탐색하고, 범위를 벗어나거나 1 이 아닌 경우 등 island('1') 가 아닌 경우에 dfs 함수 탈출.

탐색한 위치는 ‘0’ 로 바꿔준다. (이미 탐색 완료되어 섬으로 인정된 땅.)

코드

    fun numIslands(grid: Array<CharArray>): Int {
        var count = 0
        grid.forEachIndexed { xIdx, row ->
            row.forEachIndexed { yIdx, item ->
                if(grid[xIdx][yIdx] == '1') {
                    ++count
                    dfs(grid, xIdx, yIdx)
                }
            }
        }
        return count
    }
    
    private fun dfs(grid: Array<CharArray>, xIdx: Int, yIdx: Int) {
        if (xIdx < 0 || xIdx >= grid.size  || yIdx < 0 || yIdx >= grid[0].size || grid[xIdx][yIdx] != '1') 
            return
        
        grid[xIdx][yIdx] = '0'
        dfs(grid, xIdx-1, yIdx)
        dfs(grid, xIdx+1, yIdx)
        dfs(grid, xIdx, yIdx-1)
        dfs(grid, xIdx, yIdx+1)
    }

배운 점

탐색을 할 때, grid[xIdx][yIdx] = '0' 와 같이 마킹 하여 재탐색하지 않도록 한다.