23.04.06 Today’s Leetcode

1254. Number of Closed Islands (medium)

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def get(x, y):
            if x >= m or x < 0 or y >= n or y < 0:
                return -1
            return grid[x][y]

        def dfs(x, y):
            tile = get(x, y)
            if tile == 1: return True
            if tile == -1: return False
            if tile == 0:
                dirs = [1, 0, -1, 0, 1]
                grid[x][y] = 1
                for i in range(4):
                    a, b = x + dirs[i], y + dirs[i + 1]
                    if not dfs(a, b):
                        grid[x][y] = 0
                        return False
                return True
        
        count = 0
        for i in range(m):
            for j in range(n):
                if get(i, j) == 0 and dfs(i, j):
                    print(i, j)
                    count += 1

        print(grid)
        return count

사각형의 모서리 부분을 따라서 DFS

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:

        n = len(grid[0])
        m = len(grid)

        def dfs(board, r, c):
            if r <0 or c< 0 or r >=m or c >= n: return 
            if board[r][c] != 0: return 
            board[r][c] = 1
            dfs(board, r-1, c)
            dfs(board, r, c-1)
            dfs(board, r+1, c)
            dfs(board, r, c+1)


        for r in range(m):
            dfs(grid, r, 0)
            dfs(grid, r, n-1)
        
        for c in range(n):
            dfs(grid, 0, c)
            dfs(grid, m-1, c)
        
        count = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    count += 1
                    dfs(grid, r, c)

        return count

1145. Binary Tree Coloring Game (medium)

    def btreeGameWinningMove(self, root, n, x):
        c = [0, 0]
        def count(node):
            if not node: return 0
            l, r = count(node.left), count(node.right)
            if node.val == x:
                c[0], c[1] = l, r
            return l + r + 1
        return count(root) / 2 < max(max(c), n - sum(c) - 1)