a-083-pacific-atlantic-water-flow2026-08-10mediumleetcode #417neetcode150

태평양과 대서양으로의 물의 흐름

#array#depth-first-search#breadth-first-search#matrix

↗ leetcode #417 · a-083-pacific-atlantic-water-flow

문제

· problem

P.a-083-pacific-atlantic-water-flow

태평양과 대서양으로의 물의 흐름

태평양과 대서양에 인접한 m x n 크기의 직사각형 섬이 있습니다. 태평양은 섬의 왼쪽과 위쪽 경계에 접하고, 대서양은 섬의 오른쪽과 아래쪽 경계에 접합니다. 섬은 정사각형 셀로 분할된 격자로 구성되어 있습니다. m x n 정수 행렬 heights가 주어지며, heights[r][c]는 좌표 (r, c)에 있는 셀의 해수면 위의 높이를 나타냅니다. 섬은 많은 비를 받으며, 빗물은 현재 셀의 높이가 인접한 셀의 높이보다 크거나 같으면 북쪽, 남쪽, 동쪽, 서쪽의 인접한 셀로 흐를 수 있습니다. 물은 바다에 인접한 모든 셀에서 바다로 흘러갈 수 있습니다. 강우수가 태평양과 대서양 모두로 흐를 수 있는 격자 좌표의 2D 리스트 result를 반환합니다. 여기서 result[i] = [r_i, c_i]는 셀 (r_i, c_i)에서 강우수가 태평양과 대서양 모두로 흐를 수 있음을 나타냅니다.

제약

· m == heights.length
· n == heights[r].length
· 1 ≤ m, n ≤ 200
· 0 ≤ heights[r][c] ≤ 10^5

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

example 2input → output

[[1]]

[[0,0]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
물은 현재 셀과 같은 높이의 인접 셀로 흐를 수 있나요?
☐
바다에 인접한 셀이 자동으로 그 바다에 도달하나요?
☐
한 셀이 태평양과 대서양 모두에 도달할 수 있나요?
☐
물은 대각선 방향(4개 방향 제외)으로 흐를 수 있나요?
☐
알고리즘이 바다 경계에서 시작하는 이유는 무엇인가요?
☐
물은 '낮은 셀에서 높은 셀로' 흐를 수 있나요?
☐
같은 셀을 여러 번 방문할 수 있나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 그리드 크기와 바다 도달 집합 초기화

○

ROWS, COLS = len(heights), len(heights[0])

○

ROWS, COLS = len(heights[0]), len(heights)

○

pac, atl = list(), list()

○

pac, atl = dict(), dict()

step 2· 역방향 흐름 DFS 함수 정의

○

def dfs(r, c, visit, prevHeight):

○

def dfs(r, c, visit):

○

def dfs(r, c, prevHeight):

○

def dfs(r, c, visit, currHeight):

step 3· 경계, 방문, 높이 조건 검증│ 중첩

○

if (

○

if (r, c) in visit or r < 0 or c < 0 or heights[r][c] > prevHeight:

○

if ((r, c) in visit) and (r < 0) and (c < 0) and heights[r][c] < prevHeight:

○

if r == ROWS or c == COLS or r < 0 or c < 0:

step 4· 셀을 방문으로 표시하고 4개 인접 셀 탐색│ 중첩

○

visit.add((r, c))

○

visit.append((r, c))

○

if (r, c) not in visit: visit.add((r, c))

○

visit.add((r, c)); return

step 5· 태평양 경계에서 DFS 시작 (위쪽 및 왼쪽 모서리)

○

for c in range(COLS):

○

dfs(ROWS - 1, c, pac, heights[ROWS - 1][c])

○

dfs(0, c, atl, heights[0][c])

○

for c in range(COLS): dfs(0, c, pac, heights[0][c])

step 6· 대서양 경계에서 DFS 시작 (아래쪽 및 오른쪽 모서리)

○

dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])

○

dfs(0, c, atl, heights[0][c])

○

dfs(r, 0, atl, heights[r][0])

○

dfs(ROWS - 1, c, pac, heights[ROWS - 1][c])

step 7· 양쪽 바다에 모두 도달 가능한 셀 수집

○

if (r, c) in pac and (r, c) in atl:

○

if (r, c) in pac or (r, c) in atl:

○

if (r, c) in pac and (r, c) not in atl:

○

if pac.intersection(atl):

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:

        ROWS, COLS = len(heights), len(heights[0])

        pac, atl = set(), set()

        def dfs(r, c, visit, prevHeight):

            if (

                (r, c) in visit

                or r < 0

                or c < 0

                or r == ROWS

                or c == COLS

                or heights[r][c] < prevHeight

):

                return

            visit.add((r, c))

            dfs(r + 1, c, visit, heights[r][c])

            dfs(r - 1, c, visit, heights[r][c])

            dfs(r, c + 1, visit, heights[r][c])

            dfs(r, c - 1, visit, heights[r][c])

        for c in range(COLS):

            dfs(0, c, pac, heights[0][c])

            dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])

        for r in range(ROWS):

            dfs(r, 0, pac, heights[r][0])

            dfs(r, COLS - 1, atl, heights[r][COLS - 1])

        res = []

        for r in range(ROWS):

            for c in range(COLS):

                if (r, c) in pac and (r, c) in atl:

                    res.append([r, c])

        return res

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

→

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

case 2

[[1]]

→

[[0,0]]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.