1. 문제 소개

leetcode-417. Pacific Atlantic Water Flow

2. 나의 풀이법

어제 풀었던 407. Trapping Rain Water II의 방식과 비슷하게 풀었다.
분수령을 찾기 위해서 바다를 맞는 경계면부터 더 이상 올라갈 수 없는 곳까지 올라가는 방식으로 풀어보았다.

from collections import deque

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        pacific = deque()
        atlantic = deque()

        pacific_visited = [[False]*n for _ in range(m)]
        atlantic_visited = [[False]*n for _ in range(m)]

        for i in range(m):
            pacific.append((i, 0))
            pacific_visited[i][0] = True
        for j in range(n):
            pacific.append((0, j))
            pacific_visited[0][j] = True

        for i in range(m):
            atlantic.append((i, n-1))
            atlantic_visited[i][n-1] = True
        for j in range(n):
            atlantic.append((m-1, j))
            atlantic_visited[m-1][j] = True

        def bfs(q, visited):
            dirs = [(1,0),(-1,0),(0,1),(0,-1)]
            while q:
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<m and 0<=ny<n and not visited[nx][ny]:
                        if heights[nx][ny] >= heights[x][y]:
                            visited[nx][ny] = True
                            q.append((nx, ny))

        bfs(pacific, pacific_visited)
        bfs(atlantic, atlantic_visited)

        result = []
        for i in range(m):
            for j in range(n):
                if pacific_visited[i][j] and atlantic_visited[i][j]:
                    result.append([i, j])

        return result

이 경우 시간복잡도는 $O(mn)$이며, heapq와 다르게 높이를 신경쓸 이유가 없으므로 deque를 사용하는 것이 유리하다.

3. 다른 풀이법

class Solution:
    def pacificAtlantic(self, heights):
        if not heights:
            return []
        m, n = len(heights), len(heights[0])
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        
        def dfs(i, j, visited):
            visited.add((i, j))
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n:
                    if (x, y) not in visited and heights[x][y] >= heights[i][j]:
                        dfs(x, y, visited)

        pacific, atlantic = set(), set()
        for j in range(n): dfs(0, j, pacific)
        for i in range(m): dfs(i, 0, pacific)
        for j in range(n): dfs(m-1, j, atlantic)
        for i in range(m): dfs(i, n-1, atlantic)
        return list(pacific & atlantic)

다른 풀이의 경우는 dfs의 방식으로 풀었으며, 복잡도는 동일하다.
또한 방문처리를 set()으로 처리했다.
코드가 아주 간결하다.

4. 결론

어제와 같이 계속 풀어가면 감을 잡는 것이 더 쉬워질 것 같다.