Leetcode 200. Number of Islands with Python

문제

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.

m * n 2D 배열이 주어집니다.
배열에서 1은 육지를, 0은 바다를 의미합니다.
섬은 수직 / 수평 방향으로 바다가 감싸고 있는 땅을 의미합니다.
배열에서 섬의 갯수를 구하세요.

예시

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: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

섬이 총 세개 있다.

제한

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

풀이법

먼저 받아온 2차원 배열의 값을 전부 순회해야 한다.

그러다가 값이 1이 발견이 되면, 그곳엔 적어도 육지가 존재, 즉 섬이 있다는 뜻이 된다.

그러나 섬 자체는 여러 육지가 연결되어 있기 때문에, 우리가 찾은 육지와 연결된 다른 육지들을 확인할 필요가 있다.

이를 위해 나는 DFS를 사용했다.

위와 같은 지도에서 내가 찾은 육지가 * 지점이라고 할때

위 지도는 아래와 같은 그래프로 표현이 가능하다.

섬의 갯수만큼 그래프가 있는것과 동일한 것이다!

그렇기에 우리는 각각의 섬에 DFS / BFS 등의 순회 알고리즘을 사용

우리가 이 섬을 체크했다는것을 적어둔다면 똑같은 섬을 두번 체크하는 일은 없을 것이다.

def fillIsland(grid: List[List[str]], x: int, y: int, xSize: int, ySize: int):
	# 상하좌우 움직임에 대한 배열
    xm = [-1, 0, 1, 0]
    ym = [0, -1, 0, 1]
    grid[x][y] = '2'
    for i in range(4):
    	# 움직인 이후 위치와 그곳이 체크한 섬인지 바다인지 혹은 배열을 벗어났는지 체크
        xt = x + xm[i]
        yt = y + ym[i]
        if xt < 0 or xt >= xSize or yt < 0 or yt >= ySize or grid[xt][yt] != '1': continue
        
        # 아니면 그대로 DFS 진행
        fillIsland(grid, xt, yt, xSize, ySize)



class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        cnt = 0
        xSize = len(grid)
        ySize = len(grid[0])
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == '1':
                    fillIsland(grid, i, j, xSize, ySize)
                    cnt += 1
        return cnt
        

카운팅 된 섬은 1이 아닌 2가 되도록 구현했다.

나는 DFS를 사용했지만, BFS로도 구현이 충분히 가능하다!
아니, 그래프를 순회할수 있는 알고리즘이라면 어떤것이든 사용 가능할 것이다.

조금 무식하다고 생각했는데 생각보다 속도가 빨리 놀라기도 했다.