[알고리즘] 리트코드 417. Pacific Atlantic Water Flow c++ // dp

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

 

* 완탐

모든좌표에대해 모든곳을 가보면서 갈수있는지 검사함

O(N * M * N * M )

int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
vector<vector<int>> heights;
vector<vector<int>> ret;
int vis[204][204],dp[204][204]; //해당좌표에서 바다로 갈수있는지
int n,m;
int a,b;

class Solution {
public:
    //해당좌표가 pacific바다로 갈수있는지, 좌-우 탐색
    void dfs(int y, int x){
        // if(x < 0 || y < 0){ //can go pacific
        //     a=1;
        //     return;
        // }
        // if(x>=m || y>=n){ // can go atlantic
        //     b=1;
        //     return;
        // }
        if(a==1 && b==1 ){
            return;
        }
        for(int i=0;i<4;++i){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(nx < 0 || ny < 0){ //can go pacific
                a=1;
                continue;
            }
             if(nx>=m || ny>=n){ // can go atlantic
                b=1;
                continue;
            }
            //if(nx < 0 || ny < 0 || nx>=m || ny >=n) continue;
            if(heights[y][x]<heights[ny][nx]) continue;
            if(vis[ny][nx]) continue;
            vis[ny][nx]=1;
            dfs(ny,nx);
            vis[ny][nx]=1;
        }
        
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& _heights) {
        memset(dp,-1,sizeof(dp));
        ret.clear();
        heights=_heights;
        n=_heights.size();
        m=_heights[0].size();
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                memset(vis,0,sizeof(vis));
                a=0; b=0;
                dfs(i,j);
                if(a && b){
                    ret.push_back({i,j});
                }
            }
        }
        
        return ret;
    }
};

 

* dp

안되는듯?

근데, 완탐으로 되는거면 그냥 제출하면됨.

========솔루션 하나 베낌=======================

접근하다

• 이 문제에서 우리는 태평양과 직접 접하고 있는 행과 열에 만 dfs를 실행할 수 있고, 방문할 수 있는 셀에 따라 dp 배열(방문한 배열)을 사용하여 이를 메모라이즈하고, 또 다른 dp(경로 배열) 배열에는 1씩 증가하여 이동 중인 경로를 영구적으로 저장 합니다 .
• 그런 다음 대서양에서 접촉한 행과 열에 대해서만 dfs를 실행하고 이동 경로를 메모합니다. (하지만 이러한 셀에서 dfs를 실행하기 전에 방문한 배열(dp 배열)을 0으로 초기화 해야 합니다 . 또한 필수 경로 배열을 증가시킵니다.)
• 이제 셀이 있는 경로 배열(dp)에서 획득된 값은 2입니다. 즉, 거기에서 두 바다로 모두 갈 수 있다는 뜻입니다.
• 그런 다음 2차원 벡터에 2개의 경로 배열 인덱스를 수집하여 저장해야 합니다.

복잡성

• 시간 복잡도 :
  오 ( m∗N ), 최악의 경우, 모든 셀은 두 바다에 모두 도달할 수 있으며 두 번 방문하게 됩니다. 이 경우는 모든 요소가 같을 때 발생할 수 있습니다.

• 공간 복잡도:
  오 ( m∗N )대서양과 태평양 방문 세포를 표시합니다.

class Solution {
public:
   int dp[205][205]; //to check visited or not
    void dfs(int i, int j,int prevVal, vector<vector<int>>& heights, vector<vector<int>>& path){
        vector<int>v;
        if(i<0 || j<0 || i>=heights.size() || j>=heights[0].size()) return;
        if(heights[i][j] < prevVal) return ;
        if(dp[i][j] != 0) return;
        path[i][j]++;
        dp[i][j]=1;

        dfs(i, j+1, heights[i][j], heights, path);
        dfs(i, j-1, heights[i][j], heights, path);
        dfs(i+1, j, heights[i][j], heights, path);
        dfs(i-1, j, heights[i][j], heights, path);


    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> path(205, vector<int>(205, 0)); //permanantly storing the visiting cell
        vector<vector<int>> ans;
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<heights.size(); i++){
            for(int j=0; j<heights[i].size(); j++){
                if(i==0 || j==0){
                    dfs(i, j, -1, heights, path);
                }         
            }
        }
        memset(dp, 0, sizeof(dp)); //initializing the dp array with 0 again
        for(int i=0;i<heights.size(); i++){
            for(int j=0; j<heights[i].size(); j++){
                if(i==heights.size()-1 || j==heights[0].size()-1){
                    dfs(i, j, -1, heights, path);
                }

            }
        }
        //storing the indices to a 2D vector
        for(int i=0;i<heights.size();i++){
            for(int j=0;j<heights[0].size();j++){
                vector<int>v;
                if(path[i][j]==2){
                    v.push_back(i);
                    v.push_back(j);
                    ans.push_back(v); //if we put this line out of the if condition, there'll be stored some unnecessary null vector?
                }
                v.clear();

            }

        }

        return ans;

    }
};

 

*완탐(역발상)

1. 경계부터 탐색함

2. 숫자가높은쪽으로 이동(역발상)

3. 모든 좌, 상단에 대해 dfs실시 -> 갈수있는곳이 visit처리됨 A

4. 모든 우, 하단에 대해 dfs 실시 -> 갈수있는곳이 visit처리됨 B

5. A 교집합 B == 모든바다로 갈수있는 좌표임!

class Solution {
public:
    int m, n;
	// denotes cells reachable starting from atlantic and pacific edged cells respectively
    vector<vector<bool> > atlantic, pacific;
	vector<vector<int> > ans;    
    vector<vector<int> > pacificAtlantic(vector<vector<int>>& mat) {
        if(!size(mat)) return ans;
        m = size(mat), n = size(mat[0]);
        atlantic = pacific = vector<vector<bool> >(m, vector<bool>(n, false));
		// perform dfs from all edge cells (ocean-connected cells)
        for(int i = 0; i < m; i++) dfs(mat, pacific, i, 0), dfs(mat, atlantic, i, n - 1);
        for(int i = 0; i < n; i++) dfs(mat, pacific, 0, i), dfs(mat, atlantic, m - 1, i);             
        return ans;
    }
    void dfs(vector<vector<int> >& mat, vector<vector<bool> >& visited, int i, int j){        
        if(visited[i][j]) return;
        visited[i][j] = true;
		// if cell reachable from both the oceans, insert into final answer vector
        if(atlantic[i][j] && pacific[i][j]) ans.push_back(vector<int>{i, j});    
		// dfs from current cell only if height of next cell is greater
/*⬇️*/  if(i + 1 <  m && mat[i + 1][j] >= mat[i][j]) dfs(mat, visited, i + 1, j); 
/*⬆️*/  if(i - 1 >= 0 && mat[i - 1][j] >= mat[i][j]) dfs(mat, visited, i - 1, j);
/*➡️*/  if(j + 1 <  n && mat[i][j + 1] >= mat[i][j]) dfs(mat, visited, i, j + 1); 
/*⬅️*/  if(j - 1 >= 0 && mat[i][j - 1] >= mat[i][j]) dfs(mat, visited, i, j - 1);
    }
};

시간 복잡도: O(M*N) 최악의 경우 모든 셀은 두 바다에 도달할 수 있으며 두 번 방문됩니다. 이 경우는 모든 요소가 동일할 때 발생할 수 있습니다.
공간 복잡도: O(M*N) 대서양과 태평양 방문 셀을 표시합니다.

 

- dfs형식은 암기할것.

    void dfs(vector<vector<int> >& mat, vector<vector<bool> >& visited, int i, int j){        
        if(visited[i][j]) return;
        visited[i][j] = true;
		// if cell reachable from both the oceans, insert into final answer vector
        if(atlantic[i][j] && pacific[i][j]) ans.push_back({i, j});    
		// dfs from current cell only if height of next cell is greater
/*⬇️*/  if(i + 1 <  m && mat[i + 1][j] >= mat[i][j]) dfs(mat, visited, i + 1, j); 
/*⬆️*/  if(i - 1 >= 0 && mat[i - 1][j] >= mat[i][j]) dfs(mat, visited, i - 1, j);
/*➡️*/  if(j + 1 <  n && mat[i][j + 1] >= mat[i][j]) dfs(mat, visited, i, j + 1); 
/*⬅️*/  if(j - 1 >= 0 && mat[i][j - 1] >= mat[i][j]) dfs(mat, visited, i, j - 1);
		//범위체크후에 넘기면, index의 안전이 보장됨!
    }

 

https://leetcode.com/problems/pacific-atlantic-water-flow/solutions/1126938/short-easy-w-explanation-diagrams-simple-graph-traversals-dfs-bfs/