LeetCode 200. Number of Islands

파이썬 알고리즘 인터뷰 문제 32번(리트코드 200번) Number of Islands
https://leetcode.com/problems/number-of-islands/

나의 풀이1(Stack)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        seen = set()
        count = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                stack = []
                if (i, j) not in seen:
                    seen.add((i, j))
                    if grid[i][j] == "1":
                        stack.append((i, j))
                        while stack:
                            y, x = stack.pop()
                            if (y, x + 1) not in seen and 0 <= x + 1 < len(grid[0]) and grid[y][x + 1] == "1":
                                stack.append((y, x + 1))
                                seen.add((y, x + 1))
                            if (y, x - 1) not in seen and 0 <= x - 1 < len(grid[0]) and grid[y][x - 1] == "1":
                                stack.append((y, x - 1))
                                seen.add((y, x - 1))
                            if (y + 1, x) not in seen and 0 <= y + 1 < len(grid) and grid[y + 1][x] == "1":
                                stack.append((y + 1, x))
                                seen.add((y + 1, x))
                            if (y - 1, x) not in seen and 0 <= y - 1 < len(grid) and grid[y - 1][x] == "1":
                                stack.append((y - 1, x))
                                seen.add((y - 1, x))
                        count += 1
        return count

나의 풀이2(Stack, 개선)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        count = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                stack = []
                if grid[i][j] == "1":
                    grid[i][j] = "0"
                    stack.append((i, j))
                    while stack:
                        y, x = stack.pop()
                        if 0 <= x + 1 < len(grid[0]) and grid[y][x + 1] == "1":
                            stack.append((y, x + 1))
                            grid[y][x + 1] = "0"
                        if 0 <= x - 1 < len(grid[0]) and grid[y][x - 1] == "1":
                            stack.append((y, x - 1))
                            grid[y][x - 1] = "0"
                        if 0 <= y + 1 < len(grid) and grid[y + 1][x] == "1":
                            stack.append((y + 1, x))
                            grid[y + 1][x] = "0"
                        if 0 <= y - 1 < len(grid) and grid[y - 1][x] == "1":
                            stack.append((y - 1, x))
                            grid[y - 1][x] = "0"
                    count += 1
        return count

• 나의 풀이1에서 이미 방문한 지점을 기록해두기 위해 seen 집합에 기록을 하였는데 그럴 필요 없이 방문한 지점은 그리드의 값을 "0"으로 바꾸면 된다.

다른 풀이(DFS, Recursive)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        def dfs(i, j):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == "0":
                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":
                    count += 1
                    dfs(i, j)
                    grid[i][j] = "0"

        return count

배운 점

• 재귀를 이용하여 풀 수 있다.
• 재귀를 이용할 수 있을 것이라 생각은 했지만, 재귀 함수 안에서 count 값을 바꾸어야 한다고 생각해서 이리저리 하다가 잘 안되었었다. 그런데 굳이 그럴 필요가 없었다. 재귀 함수는 현재 방문한 곳과 연결된 부분을 방문했다고 처리하기만 하면 된다.

오답

• 재귀 함수 안에서 count를 업데이트 하려니 잘 안되었다.
• 분명 backtracking할 때 부모 함수의 list를 업데이트한 기억이 있는데?
• 알고보니 mutable과 immutable의 차이였다. immutable한 변수를 자식 함수에서 업데이트 하려면 nonlocal선언이 필요하다.

부모 함수 변수를 이용할 때 유의할 점, nonlocal VS global차이점
https://velog.io/@coding_study/부모-함수의-변수에-접근할-때-유의할-점