비선형 자료구조_1. Number of Islands

leetcode 200. Number of Islands

문제

1을 육지로, 0을 물로 가정한 2D 그리드 맵에서 섬의 개수를 구하라.

입출력예시

• 입력:

11110
11010
11000
00000

• 출력: 1

풀이

그리드 맵을 동서남북이 연결된 그래프로 가정하고 DFS 재귀를 이용해 그래프 탐색을 한다.

파이썬

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            # 더 이상 땅이 아닌 경우 종료
            if i < 0 or i >= len(grid) or \
                j < 0 or j >= len(grid[0]) or \
                grid[i][j] != '1':
                    return 

            grid[i][j] = 0 # 방문 마킹

            # 동서남북 탐색
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    # 모든 육지 탐색 후 카운트 1 증가
                    count += 1
        return count

• runtime: 136 ms
• memory: 15.6 MB

자바스크립트

const numIslands = function(grid) {

  const dfs = (i, j) => {
    if (i < 0 || i >= grid.length || 
        j < 0 || j >= grid[i].length || 
        grid[i][j] !== '1') {
      return;
    }

    grid[i][j] = '0';
    
    dfs(i + 1, j) // down
    dfs(i - 1, j) // up
    dfs(i, j + 1) // right
    dfs(i, j - 1) // left
  }

  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for(let j = 0; j < grid[i].length; j++) {  
      if(grid[i][j] === '1') {
        count++;
        dfs(i, j)
      }
    }
  }
  return count;
};

• runtime: 96 ms
• memory: 39.7 MB

참고
파이썬 알고리즘 인터뷰