LeetCode 417 - Pacific Atlantic Water Flow

m x n 크기의 2차원 높이 지도(Matrix)가 주어졌을 때, 태평양(Pacific)과 대서양(Atlantic) 양쪽 모두로 빗물이 흘러갈 수 있는 모든 격자 좌표를 구하는 Medium 문제다. 모든 셀에서 두 바다를 향해 각각 시뮬레이션하는 대신, 각 바다의 가장자리에서 출발하여 높은 곳으로 물을 거꾸로 거슬러 올라가는 역방향 DFS(깊이 우선 탐색)를 적용하여 O(M × N)에 해결했다.

문제 링크 & 설명

문제 링크: 417. Pacific Atlantic Water Flow
요약: 왼쪽과 위쪽 경계는 태평양, 오른쪽과 아래쪽 경계는 대서양과 맞닿아 있다. 물은 상하좌우로 현재 높이 이하인 인접 칸으로만 흐를 수 있을 때, 두 바다 모두에 도달 가능한 좌표 리스트를 반환한다.

각 셀마다 물을 흘려보는 정방향 탐색은 동일한 셀을 반복 방문하여 O((M × N)²)의 비효율이 발생한다. 반대로 바다 경계에서 출발해 “높이가 같거나 더 높은 인접 칸”으로만 퍼져나가는 역방향 탐색을 사용하면 각 바다별로 전체 격자를 한 번씩만 순회할 수 있다.

접근 방법

pacific과 atlantic 두 개의 방문 집합(Set)을 유지한다.

rows, cols = len(heights), len(heights[0])
pacific = set()
atlantic = set()

def dfs(r, c, visited, prev_height):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return

    if (r, c) in visited or heights[r][c] < prev_height:
        return

    visited.add((r, c))

    dfs(r + 1, c, visited, heights[r][c])
    dfs(r - 1, c, visited, heights[r][c])
    dfs(r, c + 1, visited, heights[r][c])
    dfs(r, c - 1, visited, heights[r][c])

역방향 DFS 정의: heights[r][c] < prev_height인 경우(즉, 이전 칸보다 낮은 곳)는 물이 거꾸로 올라갈 수 없으므로 탐색을 중단한다. 방문한 유효한 셀은 visited 셋에 추가하고 4방향으로 재귀 탐색한다.
태평양 경계 출발: 상단 행(r = 0)과 좌측 열(c = 0)의 모든 셀에서 태평양 DFS를 시작한다.
대서양 경계 출발: 하단 행(r = rows - 1)과 우측 열(c = cols - 1)의 모든 셀에서 대서양 DFS를 시작한다.
교집합 추출: 두 바다에서 모두 도달 가능한 좌표는 두 방문 셋의 교집합(pacific & atlantic)으로 구한다.

복잡도 분석

시간 복잡도: O(M × N)
- 태평양과 대서양 각각에 대해 각 셀을 최대 한 번씩만 방문하므로 전체 시간은 격자 크기에 비례한다.
공간 복잡도: O(M × N)
- 방문 셋 pacific, atlantic과 DFS 재귀 호출 스택이 최악의 경우 O(M × N) 크기를 차지한다.

구현 코드

class Solution:

    def pacificAtlantic(self, heights):
        if not heights or not heights[0]:
            return []

        rows, cols = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()

        def dfs(r, c, visited, prev_height):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return

            if (r, c) in visited or heights[r][c] < prev_height:
                return

            visited.add((r, c))

            dfs(r + 1, c, visited, heights[r][c])
            dfs(r - 1, c, visited, heights[r][c])
            dfs(r, c + 1, visited, heights[r][c])
            dfs(r, c - 1, visited, heights[r][c])

        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])

        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])

        return [[r, c] for r, c in pacific & atlantic]

요약 및 회고

그래프 탐색에서 모든 시작점에서 목적지를 찾는 것보다, 목적지(경계선)에서 시작점으로 역추적하는 발상의 전환이 시간 복잡도를 획기적으로 줄여준다. 두 집합의 교집합 연산(pacific & atlantic)으로 결과를 산출하는 구조 역시 코드를 간결하고 직관적으로 만들어준다.