Today's Challenge

https://leetcode.com/problems/pacific-atlantic-water-flow/

Pacific Atlantic Water Flow - LeetCode

어제에 이은 DFS 문제!

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        MOVES = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        
        def dfs(i, j, visited):
            visited.add((i,j))
            for di, dj in MOVES:
                x, y = i + di, j + dj
                if 0 <= x < n and 0 <= y < m and (x, y) not in visited and heights[i][j] <= heights[x][y]:
                    dfs(x, y, visited)
                    
        n, m = len(heights), len(heights[0])

        atl_visited = set()
        pas_visited = set()

        for i in range(n):
            dfs(i, 0, pas_visited)
            dfs(i, m-1, atl_visited)

        for j in range(m):
            dfs(0, j, pas_visited)
            dfs(n-1, j, atl_visited)

        return atl_visited & pas_visited