[Leetcode] 200. Number of Islands

🔗 Problem Link

Number of Islands - LeetCode

---

❔Thinking

• 0은 물, 1은 땅을 나타내는 grid가 주어질 때, 섬의 개수를 반환한다.

---

💻Solution

1. while을 활용한 DFS 풀이

def numIslands(grid: List[List[str]]) -> int:
    island = 0
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                # DFS
                stack = [(i, j)]
                while stack:
                    x, y = stack.pop(0)
                    for nx, ny in zip([-1,1,0,0], [0,0,-1,1]):
                        if 0<=x+nx<m and 0<=y+ny<n and grid[x+nx][y+ny] == '1':
                            stack.append((x+nx, y+ny))
                            grid[x+nx][y+ny] = '#'
                island += 1
    return island

 

2. 재귀를 활용한 DFS 풀이

def numIslands(grid: List[List[str]]) -> int:
	m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if 0<=i<m or 0<=j<n or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    island = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j)
                island += 1
    return island

---

🗝️keypoint

1. DFS를 통해 1로 이루어진 영역을 벗어나면 하나의 섬으로 처리한다.
2. 별도의 확인 없이, grid의 값을 0과 1이 아닌 값으로 변경하여 방문처리를 할 수 있다.