Graphs: 417. Pacific Atlantic Water Flow ★

417. Pacific Atlantic Water Flow

 

이 문제는 두 개의 대양(태평양과 대서양) 모두로 물이 흐를 수 있는 위치를 찾는 것입니다. 각 셀의 물은 다음 조건을 만족할 때 이동합니다:

1. 인접한 셀의 높이가 현재 셀보다 작거나 같아야 합니다.
2. 물이 태평양과 대서양의 경계에서 시작하여 거꾸로 퍼져 나가야 효율적으로 풀 수 있습니다.

---

문제를 해결하기 위한 접근 방식

1. 거꾸로 흐르는 관점(BFS/DFS):
   • 태평양과 대서양의 경계에서 각각 시작하여 물이 역으로 퍼져 나가는 방식으로 탐색합니다.
   • 각각의 대양에 도달할 수 있는 셀을 계산하고, 두 대양 모두에 도달 가능한 셀을 찾습니다.
2. 탐색 방향:
   • 네 방향(상, 하, 좌, 우)으로 이동하면서 물이 흐를 수 있는지 확인합니다.
   • 조건: height[다음 셀] >= height[현재 셀]이어야 합니다.
3. 경계 정의:
   • 태평양 경계: 왼쪽 열과 윗 행에서 시작.
   • 대서양 경계: 오른쪽 열과 아랫 행에서 시작.
4. 결과 계산:
   • 태평양과 대서양에서 각각 도달 가능한 셀을 기록한 후, 교집합을 구합니다.

 

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(heights), len(heights[0])
        
        # 네 방향 이동: 상, 하, 좌, 우
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        # DFS를 사용하여 대양에 도달 가능한 셀을 탐색
        def dfs(r, c, reachable):
            reachable.add((r, c))  # 현재 위치를 방문으로 처리
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < ROWS and 0 <= nc < COLS and
                    (nr, nc) not in reachable and
                    heights[nr][nc] >= heights[r][c]):  # 높이가 감소하지 않는 경우만 이동
                    dfs(nr, nc, reachable)
        
        # 태평양과 대서양에 각각 도달 가능한 셀 저장
        pacific_reachable = set()
        atlantic_reachable = set()
        
        # 태평양 경계에서 DFS 시작
        for r in range(ROWS):
            dfs(r, 0, pacific_reachable)  # 왼쪽 열
            dfs(r, COLS - 1, atlantic_reachable)  # 오른쪽 열
        for c in range(COLS):
            dfs(0, c, pacific_reachable)  # 윗 행
            dfs(ROWS - 1, c, atlantic_reachable)  # 아랫 행
        
        # 태평양과 대서양에 모두 도달 가능한 셀의 교집합
        result = list(pacific_reachable & atlantic_reachable)
        return result

 

https://youtu.be/s-VkcjHqkGI?si=ER-lkjcsFrL05Ery

 

 

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        # 행과 열의 크기
        ROWS, COLS = len(heights), len(heights[0])
        
        # 태평양과 대서양에 도달 가능한 셀을 저장할 집합
        # Sets to store cells reachable by Pacific and Atlantic oceans
        pacific, atlantic = set(), set()

        # DFS 함수 정의
        # DFS function definition
        def dfs(r, c, visit, prev_height):
            """
            r, c: 현재 위치 (row, column) / Current position
            visit: 이미 방문한 셀을 저장하는 집합 / Set to store visited cells
            prev_height: 이전 셀의 높이 / Height of the previous cell
            """
            # 유효한 범위인지 확인 (그리드 내에 존재해야 함)
            # Check if the cell is within valid range (inside the grid)
            if r in range(ROWS) and c in range(COLS) and (r, c) not in visit and heights[r][c] >= prev_height:
                # 현재 셀을 방문으로 표시
                # Mark the current cell as visited
                visit.add((r, c))
                
                # 4방향으로 이동하며 DFS 호출 (상, 하, 좌, 우)
                # Call DFS in four directions (up, down, left, right)
                dfs(r + 1, c, visit, heights[r][c])  # 아래로 / Down
                dfs(r - 1, c, visit, heights[r][c])  # 위로 / Up
                dfs(r, c + 1, visit, heights[r][c])  # 오른쪽으로 / Right
                dfs(r, c - 1, visit, heights[r][c])  # 왼쪽으로 / Left

        # 태평양 경계에서 DFS 시작
        # Start DFS from the Pacific Ocean boundary
        for r in range(ROWS):
            dfs(r, 0, pacific, heights[r][0])  # 제일 왼쪽 열 / Leftmost column
            dfs(r, COLS - 1, atlantic, heights[r][COLS - 1])  # 제일 오른쪽 열 / Rightmost column

        # 대서양 경계에서 DFS 시작
        # Start DFS from the Atlantic Ocean boundary
        for c in range(COLS):
            dfs(0, c, pacific, heights[0][c])  # 제일 위쪽 행 / Topmost row
            dfs(ROWS - 1, c, atlantic, heights[ROWS - 1][c])  # 제일 아래쪽 행 / Bottommost row

        # 태평양과 대서양에 모두 도달 가능한 셀 찾기
        # Find cells reachable by both Pacific and Atlantic oceans
        res = []
        for r in range(ROWS):
            for c in range(COLS):
                if (r, c) in pacific and (r, c) in atlantic:
                    res.append([r, c])  # 교집합에 해당하는 셀 추가 / Add cells in the intersection
        return res