leetCode 200. Number of Islands

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

 

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.

 

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

 

섬의 개수를 구하는 문제이다. input 값이 인접행렬로 주어졌다.

값이 1이면 탐색하고 더 이상 상하좌우에 1이 없으면 반환한다. 이미 방문한 곳은 다시 0으로 표기한다.

 

[로직]

# 그리드가 빈 행렬이면 0을 반환한다.

# 그리드를 줄 단위로 탐색한다.

# 방문한 칸이 1일 경우, 연결된 부분(상하좌우 붙은 1) 탐색을 시작한다. 이미 방문했으면(0이면) 패스한다.

     # 탐색하다가 주변이 더 이상 땅이 아니면 종료한다.

     # 방문한 곳은 0으로 표기한다. (방문했으니 다시 방문하지 말라는 뜻, 바다와 동일)

# 1이 연결된 곳은 전부다 탐색했으면, 섬의 개수를 추가한다.

# 옆 칸으로 이동해서 위를 반복한다. 전체 그리드를 탐색한다.

 

 

     

[구현]

#leetcode 200.Number of Islands
from typing import List

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

            # 방문한 곳은 0으로 표기한다. (방문했으니 다시 방문하지 말라는 뜻, 바다와 동일)
            grid[i][j] = 0

            # 주변을 탐색한다.
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        # 그리드가 빈 행렬이면 0을 반환한다.
        if not grid:
            return 0

        # 그리드를 줄 단위로 탐색한다. 
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):  # 옆 칸으로 이동해서 위를 반복한다. 전체 그리드를 탐색한다.
                if grid[i][j] == '1':
                    # 방문한 칸이 1일 경우, 연결된 부분(상하좌우 붙은 1) 탐색을 시작한다. 이미 방문했으면(0이면) 패스한다.
                    dfs(i, j)
                    # 1이 연결된 곳은 전부다 탐색했으면, 섬의 개수를 추가한다.
                    count += 1
        return count


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

solution = Solution()
print(solution.numIslands(grid))

 

 

 

 

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