[LeetCode] 200 | Number of Islands | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

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

---

내 풀이

자주 접할 수 있는 dfs, bfs문제다.

나는 dfs로 풀었다.

grid를 순서대로 훑으며 grid의 값이 "1"일 때 dfs를 시작한다. 이때 주의해야할 점은 int 1이 아니라 str "1"이라는 점이다.

해당 지점에서 상하좌우를 살펴 dfs를 진행하며 아직 방문하지 않은 곳이고(visited[newY][newX]==0), grid[newY][newX]의 값이 "1"이라면 그 지점에서 dfs를 시작한다.

dfs 안에서 dfs가 진행되는 것은 같은 island안에서 진행되는 것이므로 제외하고, 새로운 dfs가 시작될 때마다 새로운 island가 존재한다는 뜻이기 때문에 그때마다 ans+=1을 한다.

---

코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        H, W = len(grid), len(grid[0])
        visited = [[0]*W for _ in range(H)]
        ans = 0
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        def dfs(y, x):
            for t in range(4):
                newY, newX = y+dy[t], x+dx[t]
                
                if 0<=newY<H and 0<=newX<W and not visited[newY][newX] and grid[newY][newX]=="1":
                    visited[newY][newX] = 1
                    dfs(newY, newX)
        
        for y in range(H):
            for x in range(W):
                if not visited[y][x] and grid[y][x]=="1":
                    visited[y][x] = 1
                    dfs(y, x)
                    ans += 1
                    
        return ans