[LeetCode]number of islands (완료)

[yeonghwanjeon]

• 문제링크
• 풀이 방향
  • DFS, BFS 개념 이용하는 문제
  • Stack, Queue에 넣고 빼가며, 0으로 바꿔줌 -> O(n)

• 풀이 1

  • DFS recursive하게 품

    
    class Solution(object):
    def DFS(self, grid, r, c) :
    if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != '1' :
        return
    
    grid[r][c] = "X"
    self.DFS(grid, r-1, c)
    self.DFS(grid, r+1, c)
    self.DFS(grid, r, c-1)
    self.DFS(grid, r, c+1)

  def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ result = 0 for i in range(len(grid)) : for j in range(len(grid[0])) : if grid[i][j] == '1' : result += 1 self.DFS(grid, i, j)

  return result