[코테] 리트코드 그래프 200. Number of Islands

200. Number of Islands

문제 링크

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

문제 설명

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 == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is ‘0’ or ‘1’.

입출력 예 #1

1. Input : grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ]
2. Output : 1

입출력 예 #2

1. Input : grid = [ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ]
2. Output : 3

문제 풀이

dfs 기법으로 동서남북으로 1이 있는 지 탐색하여 1의 덩어리들의 개수를 구한다.

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 - 1, j)
            dfs(i, j + 1)
            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