leetcode.com 417. Pacific Atlantic Water Flow

문제 링크: https://leetcode.com/problems/pacific-atlantic-water-flow/description/
파이썬 소스: https://bit.ly/3wVg67g

 

Pacific과 Atlantic으로 모두 빗물이 흘러갈 수 있는 위치를 찾는 문제입니다.

정석적으로 문제를 접근해보면, heights를 이중 루프를 돌면서, 각 r, c 마다 DFS 또는BFS 방식을 사용해서 Pacific과 Atlantic으로 빗물이 흘러 들어갈 수 있는지 확인할 수 있습니다. 이렇게 구현하면 시간 복잡도는 O ((m * n) ** (m * n))이 되고요, m과 n의 최대값이 200임을 가정해보면 너무 큰 수가 나와서 시간안에 해결할 수 없습니다.

여기서, Pacific과 Atlantic으로 모두 빗물이 흘러갈 수 있는 위치를 찾는 것에서, 다른 방식으로 접근해 볼 수 있습니다. 빗물이 산에서 흘러 내려오는 것이 아니라, 바다에서 보다 높은 곳으로 거슬러 올라간다. 라고 문제를 바라보는 방식을 바꿔 보면, 시간 복잡도는 이렇게 바뀌게 됩니다.

m * n은 변함이 없지만, 시작하는 위치가 heights 배열의 테두리 4개의 직선입니다.

O ((m*n) * 2m + (m*n) * 2n) = O ((m*n) * 2(m + n))

m,n의 최대값인 200을 적용해보면,

O(40000 * 2 (200+200)) = O(40000 * 800) 정도가 되구요, 대략 10의 8제곱 정도 됩니다.

 

물이 거꾸로 거슬러 올라가서, 산으로 올라가는 것이므로, 시작지점은 heights배열의 테두리 4개의 직선입니다. 물어 거슬러 올라 갈수 있는 경우는, 인접한 height가 높거나, 높이가 같으면 물이 거슬러 올라간다고 볼 수 있습니다. 거슬러 올라가는대 사용할 dfs 함수를 알아 보겠습니다.

 

def dfs(visited: List[List], prev_height, r, c):     if 0 <= r < MAX_ROW \             and 0 <= c < MAX_COL \             and visited[r][c] == False \             and prev_height <= heights[r][c]:         visited[r][c] = True         dfs(visited, heights[r][c], r - 1, c)         dfs(visited, heights[r][c], r, c + 1)         dfs(visited, heights[r][c], r + 1, c)         dfs(visited, heights[r][c], r, c - 1)

 

dfs 함수 안에서 방문한 곳에 visited에 True로 표시해 두고, 중복방문 하지 않기 위해서, visited가 False일 때만 방문하도록 합니다.

4가지 방향 모두 방문 하도록 4번 dfs() 함수를 인접한 4개의 지정으로 호출하는 합니다.

 

for r in range(0, MAX_ROW):     dfs(pacific, 0, r, 0)     dfs(atlantic, 0, r, MAX_COL - 1)

 

문제에서 주어진 것과 같이 위에는 pacific으로 빗물이 흘러가고, 아래로는 atlantic으로 흘러갑니다. 따라서 제일 윗줄에 대해서는 pacific 배열이, 제일 아랫줄에 대해서는 Atlantic 배열이 사용합니다.

 

for c in range(0, MAX_COL):     dfs(pacific, 0, 0, c)     dfs(atlantic, 0, MAX_ROW - 1, c)

 

제일 왼쪽 줄에 대해서는 pacific 배열이, 오른쪽 줄에 대해서는 Atlantic 배열을 사용합니다.

 

from typing import List class Solution:     def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:         MAX_ROW = len(heights)         MAX_COL = len(heights[0])         pacific: List[List] = [[False for _ in range(MAX_COL)] for _ in range(MAX_ROW)]         atlantic: List[List] = [[False for _ in range(MAX_COL)] for _ in range(MAX_ROW)]         def dfs(visited: List[List], prev_height, r, c):             if 0 <= r < MAX_ROW \                     and 0 <= c < MAX_COL \                     and visited[r][c] == False \                     and prev_height <= heights[r][c]:                 visited[r][c] = True                 dfs(visited, heights[r][c], r - 1, c)                 dfs(visited, heights[r][c], r, c + 1)                 dfs(visited, heights[r][c], r + 1, c)                 dfs(visited, heights[r][c], r, c - 1)         for r in range(0, MAX_ROW):             dfs(pacific, 0, r, 0)             dfs(atlantic, 0, r, MAX_COL - 1)         for c in range(0, MAX_COL):             dfs(pacific, 0, 0, c)             dfs(atlantic, 0, MAX_ROW - 1, c)         answer: List[List] = []         for r in range(0, MAX_ROW):             for c in range(0, MAX_COL):                 if pacific[r][c] and atlantic[r][c]:                     answer.append([r, c])         return answer

 

마지막으로, pacific 배열과 Atlantic 배열이 모두 True곳의 row, col 값을 answer에 저장하고, 리턴하면 이문제의 답을 구할 수 있습니다.