[리트코드 200] DFS 탐색 문제풀이1

*DFS란? Depth-first search의 약자로 깊이 우선 탐색하는 그래프 탐색 방법 중 하나이다.

자세한 내용은 [자료구조] 그래프(Graph) 참고.

 

200. 섬의 개수 (Number of Islands)

Example

- 주어진 2D 그리드 맵(m*n)에서 '1' 은 땅을 '0'은 물로 표현했을 때 섬의 개수를 출력하라.

Constraints

- m == grid.length

- n == grid[i].length

- 1 < m, n <= 300

- grid[i][j] is '0' or '1'

Solutions

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

 

위 예제를 2차 행렬로 표현

- 4면이 모두 물('0') 인 육지('1')를 찾아야 함으로 네 방향을 각각 DFS 재귀를 이용해 탐색하는 방식으로 문제를 풀 수 있다.

- DFS 함수를 통해 땅이 아닐 때 까지 깊이 탐색한 후 탐색이 끝나면 count(섬의 개수) 를 1 증가시킨다. (재귀호출이 모두 끝나 빠져나오면 섬 하나를 반견한 것이다.)

- 한번 탐색한 곳은 마킹('v')을 통해 반복 탐색을 막는다.

 

코드 샘플 

# Python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        m = len(grid)
        n = len(grid[0])
        
        def dfs(i, j):
            # 땅이 아닌 경우 종료
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
                return
            
            # 탐색 여부 마킹
            grid[i][j] = 'v'
            
            # 4면 탐색
            dfs(i + 1, j)  # 아래
            dfs(i - 1, j)  # 위
            dfs(i, j + 1)  # 오른쪽
            dfs(i, j - 1)  # 왼쪽
        
        
        count = 0
        for i in range(m):
            for j in range(n):
                # 땅인 경우 4면 탐색을 시작한다.
                if grid[i][j] == '1':
                    dfs(i, j)
                    
                    # 모두 탐색 후 섬 개수 증가
                    count += 1
        return count

 

// kotlin
class Solution {
    fun numIslands(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size

        fun dfs(i: Int, j: Int) {
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return

            grid[i][j] = 'v'

            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        }

        var count = 0
        for (i in 0..m-1) {
            for (j in 0..n-1) {
                if (grid[i][j] == '1') {
                    dfs(i, j)

                    count++
                }
            }
        }

        return count
    }
}

실행결과

 

참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview