[1스4코2파] # 228 LeetCode 417. Pacific Atlantic Water Flow

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (228차)
[4코1파] 2023.01.13~ (220일차)
[1스4코1파] 2023.04.12~ (131일차)
[1스4코2파] 2023.05.03 ~ (109일차)

Today :

2023.08.20 [228일차]
graph
417. Pacific Atlantic Water Flow

LeetCode 417. Pacific Atlantic Water Flow

https://leetcode.com/problems/pacific-atlantic-water-flow/description/

문제 설명

태평양(Pacific Ocean)과 대서양(Atlantic Ocean)에 접해 있는 m x n 직사각형의 matrix이 주어질 때, 태평양은 섬의 왼쪽과 위쪽 가장자리에 닿고 대서양은 섬의 오른쪽과 아래쪽 가장자리에 닿는다.

섬은 정사각형 셀의 grid로 heights[r][c]가 좌표 (r, c)에서 셀의 해수면 위 높이를 나타내는 m x n 에서의 정수 값임

섬은 많은 양의 비를 받고 이웃 셀의 높이가 현재 셀의 높이보다 작거나 같으면 빗물이 이웃 셀로 직접 동서남북으로 흐를 수 있고, 물은 바다에 인접한 모든 셀에서 바다로 흐를 수 있음 ( 수평, 수직 끝까지 조건에 맞으면 간다는 것)

이때, 태평양과 대서양이 맞물리는 곳의 grid 좌표를 return

문제 풀이 방법

dfs 로 접근해서 푸는데,
대서양 및 태평양에 인접하는 곳은 주어진 matrix의 우상단 꼭대기, 좌하단 꼭대기 조건을 잘 생각해야 하고, dfs로 방문했던 좌표와 더불어 이전 높이를 기억하고 있어야, 이전높이와 비교해서 물이 흐를 수 있는지 아닌지를 체크할 수 있다.

내 코드

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, visited, prevHeight):
            if ((r,c) in visited or (r<0 or c<0 or r == rows or c == cols) or heights[r][c]<prevHeight):
                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, 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
        

증빙

여담

옆자리 훈장님 덕분에 이제 슬슬 dfs 이해가 되는 것 같은데