[LeetCode] 200. Number of Islands

😎풀이

1. grid를 2중 반복으로 순회한다.
2. 순회 중 island를 만난다면 깊이우선탐색(dfs)을 진행한다.
   2-1. 탐색 도중 이미 탐색한 island(T)를 만날 경우 중지
   2-2. 탐색 도중 바다를 만날 경우 중지
   2-3. 동 서 남 북 4방향 중 가능한 모든 방향을 순회하며 연결된 island를 임시 문자 T로 설정(재방문 방지)
3. island의 수를 증가시킨다.
4. 총 탐색된 island의 수를 반환한다.

function numIslands(grid: string[][]): number {
    let result = 0

    const m = grid.length
    const n = grid[0].length

    // 주변 island 깊이우선탐색
    function dfs(row: number, col: number) {
        const current = grid[row][col]
        if(current === 'T') return
        if(current === '0') return
        // 해당 island를 임시('Temp')로 설정
        grid[row][col] = 'T'
        if(row + 1 < m) dfs(row + 1, col)
        if(row - 1 >= 0) dfs(row - 1, col)
        if(col + 1 < n) dfs(row, col + 1)
        if(col - 1 >= 0) dfs(row, col - 1)
    }

    for(let row = 0; row < m; row++) {
        for(let col = 0; col < n; col++) {
            // island 아닌 경우 무시
            if(grid[row][col] !== '1') continue
            dfs(row, col)
            result++
        }
    }

    return result
};