417. Pacific Atlantic Water Flow

문제

그래프 탐색 문제이다. 2차원 배열의 그래프가 주어진다. 그래프는 섬을 의미한다. 각 노드의 value는 섬의 높이다. 인근 노드와의 높이 차이로 물이 흐른다. 각 노드를 시작으로 물이 흐를 때 Pacific Ocean(태평양)과 Atlantic Ocean(대서양) 까지 닿는 노드들을 찾는 문제이다.

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

Solution

class Solution {
    final int[][] d = {{-1, 0},{1, 0},{0, -1},{0, 1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {

        int m = heights.length;
        int n = heights[0].length;

        boolean[][] p_visited = new boolean[m][n];
        boolean[][] a_visited = new boolean[m][n];

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

        for(int i = 0; i<n;i++) {
            bfs(new int []{0, i}, p_visited, heights);
            bfs(new int []{m-1, i}, a_visited, heights);
        }

        for(int i = 0; i<m;i++) {
            bfs(new int []{i, 0}, p_visited, heights);
            bfs(new int []{i, n-1}, a_visited, heights);
        }


        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++) {
                if(p_visited[i][j] && a_visited[i][j])
                    answers.add(List.of(i,j));
            }
        return answers;
    }

    void bfs(int[] start, boolean[][] visited, int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;

        Queue<int[]> queue = new LinkedList<>();
        // int[][] d = {{-1, 0},{1, 0},{0, -1},{0, 1}};
        queue.offer(new int[]{start[0], start[1]});
        visited[start[0]][start[1]] = true;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();

            for(int i=0;i<4;i++) {
                int[] next = {cur[0]+d[i][0], cur[1]+d[i][1]};

                if(next[0]<0 || next[0]>=m || next[1]<0 || next[1]>=n || visited[next[0]][next[1]]) {
                    continue;
                }

                int curH = heights[cur[0]][cur[1]];
                int nextH = heights[next[0]][next[1]];

                if(curH>nextH)
                    continue;

                visited[next[0]][next[1]] = true;
                queue.offer(new int[]{next[0], next[1]});
            }
        }
    }
}

문제의 힌트는 태평양과 대서양에 닿는 가장자리 노드였다. 특정 노드에서 탐색을 시작하여 태평양 또는 대서양 까지 탐색이 가능한지 확인하는 것보다 태평양과 대서양에 닿는 것이 자명한 가장자리 노드를 시작으로 역으로 흘러가는 경로를 탐색하면 된다. 역발상이 필요한 문제였다. 역발상의 힌트는 아래와 같다.

• 문제에서 요구하는 결과는 태평양과 대서양까지 물이 흐르는(이동 가능한) 노드이다. 그 노드의 이동 경로 중 마지막은 반드시 가장자리 노드를 거치게 될 것이다.
• 이동 조건은 높이 차이였다. 높이 차로 이동하므로 역으로 가장 자리에서 높이 차를 이용해 이동 가능하다.

태평양과 닿는 가장자리 노드와 대서양과 닿는 가장자리 노드를 분리해서 bfs 탐색을 진행하였다.

참고

https://www.youtube.com/watch?v=TDXYDi2szcc