리트코드 데일리과제(3/25) - Pacific Atlantic Water Flow

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

1. 유형

BFS

 

2. 풀이

 

각 셀마다 bfs를 돌려주면 된다.

 

이때, 문제에서 요구한 조건대로, 대서양과 태평양에 닿았는지만 체크. 둘다 닿았으면 가능한 셀

---

다른 풀이

 

모범답안에서는 bfs를 단 두번만 호출해서 풀었다.

 

이런 식으로 태평양에서 bfs를 돌려주고, 대서양에서 bfs를 돌려서 경계선을 구한다.

 

matix를 탐색하며 경계선만 체크해주면 된다.

 

3. 코드

class Solution {
    static boolean visit[][];
    static int dr[] = {-1,1,0,0};
    static int dc[] = {0,0,-1,1};
    static int rowSize, colSize;
    static int map[][];
    static boolean bfs(int r, int c){
        boolean p = false;
        boolean a = false;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r,c});
        visit[r][c] = true;
        while(!q.isEmpty()){
            int cur[] = q.poll();
            for(int i=0; i<4; i++){
                int nr = cur[0]+dr[i];
                int nc = cur[1]+dc[i];
                if(nr<0 || nc<0){
                    p = true;
                    continue;
                }
                if(nr >= rowSize || nc >= colSize){
                    a = true;
                    continue;
                }
                if(visit[nr][nc] || map[cur[0]][cur[1]] < map[nr][nc] ) continue;
                visit[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
        if(a && p)
            return true;
        else
            return false;
    }
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> list = new ArrayList<>();
        if(matrix.length==0){
            
        }else{
            rowSize = matrix.length;
            colSize = matrix[0].length;
            map = matrix;
            for(int i=0; i<rowSize; i++){
                for(int j=0; j<colSize; j++){
                    visit = new boolean[rowSize][colSize];
                    if(bfs(i, j)){
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        temp.add(j);
                        list.add(temp);
                    }
                }
            }
        }
        return list;
    }
}