[Leetcode] Number of Islands (python) , dfs 풀이

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

 

 

풀이 아이디어

- 대각선은 섬이 아니다.

- 가로세로로 연결된 모든 1을 0으로 바꾸고 카운트 변수를 증가시키자.

- dfs 함수의 베이스 케이스는, 함수가 언제 끝나는지 + 그리드 벗어나지 않게 범위 내에 있는지 체크

- 테스트 케이스를 일부만 통과하길래 왜지하고 고민했는데 dy 값 하나가 음수여서 그런 것이었다. 왜 눈에 안보였을까..ㅎ 역시 휴먼에러.. 

 

풀이

class Solution:

    dx = [0,1,0,-1]
    dy = [-1,0,1,0]
    
    def numIslands(self, grid: List[List[str]]) -> int:
        
        cnt = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' :
                    self.dfs(grid,i,j)
                    cnt += 1

        return cnt
            
    def dfs(self, grid, i, j) :
        if i<0 or i>= len(grid) or j<0 or j>= len(grid[0]) or grid[i][j] == '0':
            return
        
        grid[i][j] = '0'
        
        for k in range(4):
            self.dfs(grid, i+self.dx[k], j+self.dy[k])

 

 

 

추가로 풀어볼 문제 (DFS) 

https://school.programmers.co.kr/learn/courses/30/lessons/42839

https://leetcode.com/problems/cousins-in-binary-tree-ii/description/

https://leetcode.com/problems/cousins-in-binary-tree/

 

 

출처: 

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