[LeetCode] 200. Number of Islands [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Number of Islands - LeetCode>

1. 문제 (섬의 개수)

주어진 맵에서 1을 육지, 0을 물로 가정하였을 때, 섬의 개수를 구하여라.

2. 풀이

DFS를 이용한 풀이

3. 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        dx = [0, 0, -1, 1]
        dy = [-1, 1, 0, 0]
        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'

            for x in range(4):
                dfs(i+dx[x], j+dy[x])

        ret = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    ret += 1

        return ret

• 결과 :

방식	Status	Runtime	Memory	Language
그래프 (DFS)	[Accepted]	156 ms	15.4 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋