Problem Solving/Leetcode

LeetCode[417] - Pacific Atlantic Water Flow

문제 LeetCode 417 : Pacific Atlantic Water Flow 풀이 일반적으로 모든 점에 대해서 DFS / BFS를 통해서 전체 탐색하는 방법이 있을 것이다. 그러나 위와 같은 방법에서는 시간복잡도를 줄이고자 다른 방법으로 접근하였다. Pacific Ocean과 맞닿아 있는 지역들을 DFS 시작 점으로 잡는다. 각 지역에서 현재 위치한 지역보다 높이가 같거나 높은 지역을 기준으로 DFS를 실행한다. DFS를 완료한 후에 전부 visited 배열을 표시하면, Pacific Ocean에 도달할 수 있는 지역들이 표시된다. 같은 방법으로 Atlantic Ocean에 도달할 수 있는 지역을 구한다. 두 지역에 모두 도달할 수 있는 겹치는 지역을 구해서 출력한다. 코드 def search(he..