리트코드 417 Pacific Atlantic Water Flow (파이썬)

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

Pacific Atlantic Water Flow - LeetCode

 

• 각 좌표들이 갈 수 있는 경우는 인접한 좌표가 자기보다 낮은 수를 가지고 있어야 한다.
• 그렇게 이동하다 맨 왼쪽 또는 제일 위, 맨 오른쪽 또는 제일 아래에 도달하면, 두 바다를 갈 수 있다.

 

---

풀이 및 해설(주석)

class Solution(object):
    def pacificAtlantic(self, heights):
        N, M = len(heights), len(heights[0])
        # pac = Pacific Ocean으로 갈 수 있는 좌표, atl = Atlantic으로 갈 수 있는 좌표
        pac, atl = set(), set()

        def dfs(r, c, visit, prevHeight):
            # 현재 위치가 visit에 있거나, 경계를 벗어나거나, 전의 위치보다 작으면 return
            if ((r, c) in visit or r < 0 or c < 0 or r == N or c == M 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])

        
        # 2차원 배열의 각 테두리 부분 위치에서 dfs탐색 시작
        for i in range(M):
            dfs(0, i, pac, heights[0][i])
            dfs(N - 1, i, atl, heights[N-1][i])

        for r in range(N):
            dfs(r, 0, pac, heights[r][0])
            dfs(r, M - 1, atl, heights[r][M-1])

        rst = []
        for r in range(N):
            for c in range(M):
                # (r, c)가 pac과 atl에 동시에 존재하면 그 좌표는 두 바다를 갈 수 있음
                if (r, c) in pac and (r, c) in atl:
                    rst.append([r, c])
        return rst

 

---

후기

• 모든 좌표에 대해 탐색을 하는 건 효율적이지 못하다. 
• 행이 0 또는 열이 0 이면 Pacific Ocean로 갈 수 있다는 뜻이고, 
• 행이 N-1 또는 열이 M-1이면 Atlantic Ocean로 갈 수 있다
• 이 정보를 가지고 이 네 부분에 대해 역으로 타고 올라가면 된다.