[LeetCode/Python] 200. 섬의 개수(Number of Islands)

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.

(연결되어 있는 1의 덩어리의 개수를 구하라.)

 

Example:

 

Input: grid =

[ ["1", "1", "1", "1", "0"],

["1", "1", "0", "1", "0"],

["1", "1", "0", "0", "0"],

["0", "0", "0", "0", "0"] ]

 

Output: 1

 

 

 

** 깔끔한 답안 **

 

 

 

1. DFS로 그래프 탐색

 

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
            grid[i][j] = 0
            # 동서남북 탐색
            dfs(i - 1, j)
            dfs(i, j - 1)
            dfs(i + 1, j)
            dfs(i, j + 1)
 
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    dfs(i, j)
                    # 모든 육지 탐색 후 카운트 1 증가
                    count += 1
        return count
 

 

 

해설:

 

그래프 모양은 아니지만 그래프 형으로 변환하여 풀 수 있는 문제이다.

 

동서남북이 모두 연결된 그래프라 가정하고 육지가 아니면 return을 이용하여 빠져나온다.

 

이 코드에서는 grid를 dfs 함수에서도 바로 쓸 수 있게 하기 위해 함수를 중첩하였다.