LeetCode: 417번 (Pacific Atlantic Water Flow) [JAVA]

문제 링크

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

Pacific Atlantic Water Flow - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. BFS 탐색을 위한 데이터 클래스 생성
2. 2개의 영역(Pacfic Ocean, Atlantic Ocean)에서 동일한 BFS 탐색 진행
   1. 각 영역과 인접한 물 타일에 대해 모두 큐에 add
   2. 이후 BFS 탐색을 통해 물이 흘러 내려올 수 있는, 즉 현재 위치보다 다음 높이가 더 높거나 같은 지역들을 모두 표시하는 과정을 진행
3. 이후 2개의 방문 배열을 동시에 방문 표시가 된 영역(양쪽 바다로 모두 물이 흘러 내려갈 수 있는 위치)들만 List<List<Integer>>에 넣어 반환

 문제에서 요구하는 부분은 특정 영역에서 시작된 물이 양쪽 바다(Pacfic Ocean, Atlantic Ocean)로 모두 흘러갈 수 있는 지를 판단해 이들을 모아 반환하는 것이다. 다만 문제대로 해결 로직을 작성할 경우 로직이 복잡해져, 이를 단순화하기 위해 

해결 방법을 다르게 할 필요가 있다.
 결국 핵심은 물이 흘러 내려가 특정 영역에 당도한다는 것이기 때문에, 이 조건을 뒤집어 현재 위치의 물이 어디서 왔는지를 반대로 탐색하면 된다. 즉 문제에서 요구하는 바다(Pacfic Ocean, Atlantic Ocean)에서부터 거꾸로 탐색을 진행해 위치가 더 높은 곳으로 BFS 탐색을 진행하면 된다. 그리고 그 이후엔 2차원 배열의 전체를 돌며 양쪽 바다에서 모두 BFS 탐색을 통해 닿은 위치라면 이는 해당 위치에서 시작된 물이 양쪽 바다로 모두 흘러갈 수 있다는 뜻이기 때문에, 해당 위치를 정답 List에 담아 이를 반환하면 된다.

 

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;

        boolean[][] visitedFromPacificOcean = new boolean[m][n],
                visitedFromAtlanticOcean = new boolean[m][n];

        List<List<Integer>> answer = new ArrayList<>();

        //Pacfic Ocean에서 거슬러 올라가며 탐색
        Queue<Position> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {//바다와 인접한 부분 추가
            q.add(new Position(i, 0, -1));
        }

        for (int i = 0; i < n; i++) {//바다와 인접한 부분 추가
            q.add(new Position(0, i, -1));
        }

        while (!q.isEmpty()) {
            Position point = q.poll();

            if (point.r < 0 || point.r >= m || point.c < 0 || point.c >= n
                    || visitedFromPacificOcean[point.r][point.c]) {//맵 밖이거나 중복 방문인 경우
                continue;
            }

            if (heights[point.r][point.c] < point.postHeight) {//이전 높이보다 낮은 경우
                continue;
            }

            visitedFromPacificOcean[point.r][point.c] = true;

            q.add(new Position(point.r + 1, point.c, heights[point.r][point.c]));
            q.add(new Position(point.r - 1, point.c, heights[point.r][point.c]));
            q.add(new Position(point.r, point.c + 1, heights[point.r][point.c]));
            q.add(new Position(point.r, point.c - 1, heights[point.r][point.c]));
        }

        //Atlantic Ocean에서 거슬러 올라가며 탐색
        q = new LinkedList<>();

        for (int i = 0; i < m; i++) {//바다와 인접한 부분 추가
            q.add(new Position(i, n - 1, -1));
        }

        for (int i = 0; i < n; i++) {//바다와 인접한 부분 추가
            q.add(new Position(m - 1, i, -1));
        }

        while (!q.isEmpty()) {
            Position point = q.poll();

            if (point.r < 0 || point.r >= m || point.c < 0 || point.c >= n
                    || visitedFromAtlanticOcean[point.r][point.c]) {//맵 밖이거나 중복 방문인 경우
                continue;
            }

            if (heights[point.r][point.c] < point.postHeight) {//이전 높이보다 낮은 경우
                continue;
            }

            visitedFromAtlanticOcean[point.r][point.c] = true;

            q.add(new Position(point.r + 1, point.c, heights[point.r][point.c]));
            q.add(new Position(point.r - 1, point.c, heights[point.r][point.c]));
            q.add(new Position(point.r, point.c + 1, heights[point.r][point.c]));
            q.add(new Position(point.r, point.c - 1, heights[point.r][point.c]));
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visitedFromPacificOcean[i][j] && visitedFromAtlanticOcean[i][j]) {//조건에 해당하는 경우
                    answer.add(List.of(i, j));
                }
            }
        }

        return answer;
    }

    class Position{//데이터 클래스
        int r, c, postHeight;

        public Position(int r, int c, int postHeight) {
            this.r = r;
            this.c = c;
            this.postHeight = postHeight;
        }
    }
}

결과