[LeetCode] 200. Number of Islands

Medium

Given an m x n 2d grid 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.

 

 

Example 1:

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

Output: 1

 

 

Example 2:

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

Output: 3

 

 

나의 코드

import numpy as np

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        num = 0
        h, w = len(grid), len(grid[0])
        visited = np.zeros((h, w), bool)
        for i in range(h):
            for j in range(w):
                if not visited[i, j]:
                    if grid[i][j] == "1":
                        dfs(grid, visited, (i, j))  # 좌표를 튜플로 저장
                        num += 1

        return num

    
def bfs(grid, visited, start):
    h, w = len(grid), len(grid[0])
    q = [start]
        
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    while len(q) > 0:
        e = q.pop()
        visited[e] = True
        
        for k in range(len(dx)):
            nx, ny = (e[0] + dx[k]), (e[1] + dy[k])
            if (0 <= nx < h and 0 <= ny < w) and (grid[nx][ny] == "1") and (not visited[nx, ny]):
                q.append((nx, ny))

• BFS로 해결
• 방문하지 않은 and "1"인 좌표에 대해 깊이 탐색을 수행
• 깊이 탐색을 수행할 때마다 섬의 개수 += 1 # num
• dx, dy를 이용 → 좌표 용이
• dfs 함수: start 좌표의 4-neighbors를 방문하면서 "1"인 grid 좌표 탐색 ▷ 찾은 좌표에 대해 다시 방문 및 탐색

 

 

- medium...까지는 아닌 듯하다.