Pacific Atlantic Water Flow

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

Pacific Atlantic Water Flow - LeetCode

 

주어진 좌표가 두 가지 해역으로 둘러 쌓여있고, 높이 값일 때 높은 곳에서 낮은 곳으로 홍수로 인해 물이 흐른다. 이 때 양쪽 해역으로 물이 다 흐르는 좌표를 찾는 문제이다.

 

물이 흐를 수 있다는 것은 각 해변 좌표 쪽까지 도달할 수 있다는 것이다. 그렇기 때문에 역으로 해변 쪽 좌표에서 높아 지는 좌표들을 체크한다면 정답 좌표들을 찾아 나갈 수 있다. 이 때 해역이 두 가지 이므로 visited 배열을 두 가지 사용한 이후 두 visited 모두를 확인하여 정답 목록을 체크할 수 있다. bfs방식으로 그래프를 탐색했으면 완성 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> pacificAtlantic(int[][] heights) {  
        int m = heights.length;  
        int n = heights[0].length;  
        boolean[][] pacific = new boolean[m][n];  
        boolean[][] atlantic = new boolean[m][n];  
        List<List<Integer>> answer = new ArrayList<>();  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                // pacific,북쪽  
                if(i == 0){  
                    bfs(i, j, heights, pacific);  
                // pacific,서쪽  
                }else if(j == 0){  
                    bfs(i, j, heights, pacific);  
                }  
  
                // atlantic,동쪽  
                if(i == m - 1){  
                    bfs(i, j, heights, atlantic);  
                // atlantic,남쪽  
                }else if(j == n - 1){  
                    bfs(i, j, heights, atlantic);  
                }  
            }  
        }  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j <n; j++){  
                if(pacific[i][j] && atlantic[i][j]) answer.add(List.of(i, j));  
            }  
        }  
  
        return answer;  
    }  
  
    private void bfs(int r, int c, int[][] heights, boolean[][] visited){  
        int[] dr = {-1,0,1,0};  
        int[] dc = {0,-1,0,1};  
  
        Queue<int[]> que = new ArrayDeque<>();  
        que.add(new int[]{r, c});  
  
        while(!que.isEmpty()){  
            int[] now = que.poll();  
            int row = now[0];  
            int col = now[1];  
            if(visited[row][col]){  
                continue;  
            }  
  
            visited[row][col] = true;  
  
            for(int dir = 0; dir < 4; dir++){  
                int nextRow = row + dr[dir];  
                int nextCol = col + dc[dir];  
  
                if(nextRow >= 0 && nextRow < heights.length  
                        && nextCol >= 0 && nextCol < heights[0].length  
                        && !visited[nextRow][nextCol]  
                        && heights[nextRow][nextCol] >= heights[row][col]){  
                    que.add(new int[]{nextRow, nextCol});  
                }  
            }  
  
        }  
    }  
  
}