[Leet code] 200. Number of Islands

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags	grid
난이도	★★
발행 여부
사이트	Leet code
실수 유형	문제 조건 미숙지
이해	완벽히 이해
최종 편집 일시	@2021년 11월 25일 오후 10:23
푼 날짜	@2021년 11월 25일 오후 10:01

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드

퇴고

문제 해설 및 주의사항

원문

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.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

번역 및 주의사항

2차원 grid 가 주어진다.

'1' 은 땅

'0' 은 물

을 나타낸다.

섬의 개수를 반환해라.

---

풀이

내 풀이 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        dx = [1, -1, 0, 0]
        dy = [0, 0, -1, 1]
        
        def dfs(y: int, x: int) -> None:
            # Check visit (y, x)
            grid[y][x] = '0'
            
            # Visit neighbors
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                # If, (ny, nx) is in range
                if (ny >= 0 and ny < n and nx >= 0 and nx < m) and grid[ny][nx] == '1':
                    dfs(ny, nx)
    
        ans = 0
        for y in range(n):
            for x in range(m):
                # If (y, x) is land
                if grid[y][x] == '1':
                    dfs(y, x)
                    ans += 1
        return ans

• 연결 요소의 개수 문제와 같았다.

---

퇴고

• 풀이 중, 두 가지 실수가 있었다.
  • dy, dx 를 적용할 때, 이중 for 문을 적용하여 dy dx 에 대해 4개의 상하좌우 좌표를 적용한 것이 아니라 16개의 좌표에 대해 탐색하고 말았다.
  • grid[y][x] 의 값이 1 과 같다고 한 것.
    • grid[y][x] 의 값은 "1" 과 같다.
    • 문제를 잘 읽자