(Graph, Medium) Pacific Atlantic Water Flow

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

이런 문제는 재밌어 보인다.

2중 for문 돌면서 특정 [r][c] 인덱스에 있는 정점으로부터 출발해
Pacific과 Atlantic에 모두 닿을 수 있는지 체크하면 될 것 같다.

그럼 Pacific에 닿는다는 것과 Atlantic에 닿는다는 것을 정리할 필요가 있다.
heights는 m x n 이라고 했으므로

visitPacific - [0][c] 또는 [r][0]
visitAtlantic - [m-1][c] 또는 [r][n-1]

코드는 어렵지 않으니 별다른 말 없이 첨부

class Solution {

    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> answer = new ArrayList<>();

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

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (canFlow(heights, i, j, m, n)) {
                    List<Integer> coordinate = new ArrayList<>();
                    coordinate.add(i);
                    coordinate.add(j);
                    answer.add(coordinate);
                }
            }
        }
        return answer;
    }

    public boolean canFlow(int[][] heights, int r, int c, int m, int n) {
        boolean visitPacific = false;
        boolean visitAtlantic = false;

        boolean[][] visited = new boolean[m][n];

        // int[] - index 0: r, 1: c
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{ r, c });

        while (!que.isEmpty()) {
            int[] coordinate = que.poll();
            int x = coordinate[0];
            int y = coordinate[1];

            visited[x][y] = true;
            int currentHeight = heights[x][y];
            
            if (x == 0 || y == 0) {
                visitPacific = true;
            }
            if ((x == m - 1) || (y == n - 1)) {
                visitAtlantic = true;
            }
            if (visitPacific && visitAtlantic) {
                return true;
            }

            for (int i=0; i<4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
                boolean possibleRange = nextX >= 0 && nextX < m && nextY >= 0 && nextY < n;
                if (possibleRange) {
                    boolean possibleHeight = currentHeight >= heights[nextX][nextY];
                    if (possibleHeight && !visited[nextX][nextY]) {
                        que.offer(new int[]{ nextX, nextY });
                    }
                }
            }
        }
        return false;
    }
}

이 방식대로 했을 때 동작은 하지만 2개 케이스에서 timeout이 발생한다.
아무래도 모든 좌표를 한 번 씩 다 탐색하면서 이어나가기 때문인 것 같다.

고민을 좀 하다가 솔루션 참고했는데
가능성이 있는 4가지 케이스로 먼저 맵을 만들어 두는 것 같다.
pacific 인접 - first row, first column
atlantic 인접 - last row, last column

이렇게 하는 경우 확실하게 닿을 수 있는 위치부터 탐색을 이어가기 때문에
내 기존 코드처럼 아무데도 못 가는 케이스를 굳이 돌아볼 필요가 없어진다.

교훈: 탐색 시작점에 대해 충분히 고민해보자.

(코드 수정해서 여기 붙여넣기)