[LeetCode] 200. Number of Islands

문제

 

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.

 

섬은 수평과 수직으로 땅이 연결되어있고, 물로 둘러싸여있는 것으로 가정함. 또한 grid 네개의 가장자리는 모두 물로 둘러싸여있다는 것을 가정. 

 

제약조건

• m == grid.length (2차원 배열의 원소가 m개 (row))
• n == grid[i].length (column의 갯수)
• 1 <= m, n <= 300 (m도 300, n도 300개가 될 수 있음. 총 9만개가 원소로 있을 수 있다는 의미. 약 10^5. O(N^2)으로는 못 품. 10의 8승을 넘어서면 시간초과가 됨 => O(NlogN)이나 O(N)으로 풀 수 있음을 알 수 있음)
• grid[i][j] is '0' or '1'

 

 

입출력 예시

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

 

 

 

풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    # def numIslands(grid):
        number_of_islands = 0
        m = len(grid) # row
        n = len(grid[0]) # column
        visited = [[False]*n for _ in range(m)] # 2차원 배열이 만들어지면서 한 행이 다 false가 됨


        # 함수 안의 함수 형식으로 bfs 함수 생성(위의 인스턴스 참조위해)
        def bfs(x, y):
            # 동서 남북 표현 (상화좌우 이동 표현)
            dx = [-1, 1, 0, 0] # (상하좌우 표현=>암시적 그래프 표현)
            dy = [0, 0, -1, 1]
            
            visited[x][y] = True
            queue = deque() 
            queue.append((x, y)) # 튜플 형식으로 x,y 원소 추가

            while queue:
                cur_x, cur_y = queue.popleft()
                for i in range(4): # 상화좌우 이동
                    next_x = cur_x + dx[i]
                    next_y = cur_y + dy[i]
                    # if 방문하면 안되는 애들 좌표 (상하좌우에서 참조할 수 없으면 에러남, 물인곳, 이미 방문한 곳)
                    if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n:
                        if grid[next_x][next_y] == "1" and not visited[next_x][next_y]: 
                            visited[next_x][next_y] = True
                            queue.append((next_x, next_y))

        for i in range(m):
            for j in range(n):
                # if 땅? & 방문안한거
                if grid[i][j] == "1" and not visited[i][j]:
                    bfs(i, j)
                    number_of_islands += 1
                # bfs or dfs 수행

        return number_of_islands

 

 

 

 

 

 

 

 

 

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

Number of Islands - LeetCode