[LeetCode] 417 | Pacific Atlantic Water Flow | Python

---

문제 링크: https://leetcode.com/problems/pacific-atlantic-water-flow/

---

문제

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

 

Example 1:

---

조건

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= $10^5$

---

내 풀이

왼쪽부터 오른쪽, 오른쪽부터 왼쪽, 위에서 아래, 아래에서 위, 네 방향으로 쭉 훑으며 이전보다 높이가 높은 곳만 visited에 표시한다.

Pacific은 왼쪽이랑 위, Atlantic은 오른쪽과 아래에 닿아있으므로 왼쪽에서 오른쪽, 위에서 아래를 표시한 visited1과 오른쪽에서 왼쪽, 아래에서 위를 표시한 visited2에서 동시에 표시된 부분을 ans로 리턴한다.

---

코드

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        H, W = len(heights), len(heights[0])
        
        visited1 = [[0]*W for _ in range(H)]
        visited2 = [[0]*W for _ in range(H)]
        dy = [0, 0, 1, -1]
        dx = [1, -1, 0, 0]
        
        ans = []
        
        def DFS(y, x, visited, prev):
            if 0<=y<H and 0<=x<W and visited[y][x]==0 and heights[y][x]>=prev:
                visited[y][x] = 1
                
                for t in range(4):
                    newY, newX = y+dy[t], x+dx[t]
                    DFS(newY, newX, visited, heights[y][x])
        
        for y in range(H):
            DFS(y, 0, visited1, 0)
            DFS(y, W-1, visited2, 0)
        for x in range(W):
            DFS(0, x, visited1, 0)
            DFS(H-1, x, visited2, 0)
        
        for y in range(H):
            for x in range(W):
                if visited1[y][x]==1 and visited2[y][x]==1:
                    ans.append([y, x])
        
        return ans