[LeetCode] 417. Pacific Atlantic Water Flow (Java)

문제

 

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

Pacific Atlantic Water Flow - LeetCode

 

풀이

 

난이도: Medium 

 

처음에는 해석하는데 애를 먹었는데 height above sea level이 해발고도를 의미하는 것이었다.

태평양(Pacific)과 대서양(Atlantic)으로 둘러싸인 섬의 각 좌표의 해발고도가 주어지고 물은 같거나 낮은 곳으로만 흐를 수 있다면, 비가 올 때 빗물이 태평양과 대서양 양쪽으로 흐를 수 있는 좌표를 구하는 문제이다. 

 

처음에는 섬의 모든 위치에서 2번의 DFS로 태평양과 대서양에 접근이 가능한지 여부를 저장하려 했다.

(BFS로는 이전의 값이 바다에 접근할 수 있는지 저장할 수 없기 때문에 배제했다.)

하지만 이는 중복된 계산을 두 번 할 뿐만 아니라 최악의 경우 40,000개의 좌표가 모두 함수 callStack에 들어가 스택 오버 플로우가 발생할 수 있다.

 

이 문제의 핵심은 바로 역으로 바다에서 섬의 각 좌표로 접근 가능한지 계산해 보는 것이다.

섬에서 시작하는 경우는 물줄기가 최종적으로 바다에 도달 가능한지 확인해야 하기 때문에 DFS를 사용할 수밖에 없었지만, 바다에서 시작하면 DFS나 BFS로 접근이 되는 좌표는 바로 저장을 해주면 된다.

따라서 훨씬 효율적인 구현이 가능하다.

 

구현 시 태평양과 대서양에서 시작하는 BFS 나 DFS를 두번 구현해 주면 된다.

 

 

BFS 구현 코드