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개의 경로 배열 인덱스를 수집하여 저장해야 합니다.
복잡성
- 시간 복잡도 :
, 최악의 경우, 모든 셀은 두 바다에 모두 도달할 수 있으며 두 번 방문하게 됩니다. 이 경우는 모든 요소가 같을 때 발생할 수 있습니다.
- 공간 복잡도:
대서양과 태평양 방문 세포를 표시합니다.
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의 안전이 보장됨!
}
'Algorithm > dfs' 카테고리의 다른 글
| 리트코드 1325 리프노드지우기 c++ (0) | 2024.05.17 |
|---|---|
| 백준 14888 연산자끼워넣기 c++ // dfs (0) | 2024.03.20 |
| 백준 14889 스타트와링크 c++ // dfs, 사람기준으로 생각하라. 일단 모든경우의수를 벌려놓고 생각하라 (0) | 2024.03.20 |
| 백준 2573 빙산 c++ // dfs, 구현, year에 대해 반복문 만들기 (0) | 2024.03.10 |
| 프로그래머스 소수찾기 c++ // 순열 3P1+3P2+3P3 하는방법, 소수판별함수, dfs (0) | 2023.12.04 |