Pacific Atlantic Water Flow

추천으로 받은 좋은 문제다. 처음에 너무 다른 접근을 했어서 상당히 애를 먹었고, 풀어 본 후에 오답인걸 확인하고 답을 참고해서 다시 풀었다.

이 문제는 좀 넓게 보고 해석할 줄 알아야 한다. 메트릭스에 나와있는 숫자가 이동하려는 숫자보다 크다면은 물이 흐를 수 있다.

그리고 이 문제는 이렇게 물이 흘러갔을 때.. 상단과 왼쪽에 Pacific 에 닿을 수 있고, 하단과, 오른쪽에 Atlantic 과 닿을 수 있는 구간을 요구한다.

class Solution {


public:
    void dfs(vector<vector<int>>& heights, int i, int j, bool& pacific, bool& atlantic, int& compare, vector<vector<bool>>& visited){
        if(i < 0 || j < 0) {pacific = true; return;}
        else if(i >= heights.size() || j >= heights[0].size()) {atlantic = true; return;} 
        else if( heights[i][j] > compare || visited[i][j]) return; 
        // if(i < 0 || j < 0 || i >= heights.size() || j >= heights[0].size() || heights[i][j] > compare || visited[i][j]){
        //     if(i < 0 || j < 0) pacific = true; 
        //     else if(i >= heights.size() || j >= heights[0].size()) atlantic = true;
        //     return; 
        // }
        visited[i][j] = true; 
        //cout << i << ' ' << j << ' ' << compare << ' ' << heights[i][j] << endl; 
        dfs(heights,i+1,j,pacific,atlantic,heights[i][j], visited); 
        dfs(heights,i-1,j,pacific,atlantic,heights[i][j], visited); 
        dfs(heights,i,j+1,pacific,atlantic,heights[i][j], visited); 
        dfs(heights,i,j-1,pacific,atlantic,heights[i][j], visited); 
    }
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> answer; 
        //bool visited[heights.size()][heights[0].size()]; 
        for(int i = 0; i< heights.size(); i++){
            for(int j = 0; j < heights[0].size(); j++){
                bool pacific, atlantic = false; 
                vector<vector<bool>> visited(heights.size(),vector<bool>(heights[0].size(),false)); 
                //memset(visited,false,sizeof(visited)); 
                dfs(heights,i,j,pacific,atlantic, heights[i][j], visited); 
                if(pacific && atlantic) answer.push_back({i,j}); 
            }
        }
        return answer; 
    }
};

틀린 풀이:
Pacific 과 Atlantic 을 True / False 로 가져가서 만약에 보더를 초과했을때 그 조건에 따라서 True / False를 나누려고 했다. 그런데 이 접근은 매우 틀렸다... 내가 분명 어떤 조건에서 틀리고 있는게 분명하다.

class Solution {


public:
    void dfs(vector<vector<int>>& heights, int r, int c, int& m, int& n, vector<vector<int>>& ocean) {
        int DIR[][2] = { {0,-1}, {1, 0}, {0, 1}, {-1, 0} }; // left, up, right, down

        for (int i = 0; i < 4; i++) {
            int nr = r + DIR[i][0], nc = c + DIR[i][1];
            // invalid index or visited
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || ocean[nr][nc] == 1) 
                continue;

            if (heights[nr][nc] >= heights[r][c]) {
                ocean[nr][nc] = 1; // visited & can flow
                dfs(heights, nr, nc, m, n, ocean); 
            } 
        }
    }

public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size(); 
        
        vector<vector<int>> pacific(m,vector<int>(n,-1)), atlantic(m,vector<int>(n,-1));  

        for(int i = 0; i < m; i++){ //영역 표시 
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0) 
                    pacific[i][j] = 1; 
                if(i == m-1 || j == n-1)
                    atlantic[i][j] = 1; 
            }
        }

        for (int i = 0; i < m; i++) { //Pacific 이랑 Atlantic 에서 루트 설정
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] == 1)
                    dfs(heights, i, j, m, n, pacific);
                if (atlantic[i][j] == 1)
                    dfs(heights, i, j, m, n, atlantic);
            }
        }


        vector<vector<int>> result;
        for (int i = 0; i < m; i++) { //서로의 루트에서 겹치는 경로가 있다면 답에 추가
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] == 1 && atlantic[i][j] == 1)
                    result.push_back({i, j});
            }
        }

        return result;
    }
};

3영역으로 나눈 풀이고 훨씬 깔끔하다. 나중에 다시 풀어봐야겠다.

---

다시 풀어봤다. 이 문제는 조금 특이하게도 다음에 탐색할 부분의 값을 알아야지 그곳으로 이동할지 / 이동하지 않을지를 판단할 수 있다. 그런데 내가 보통 하는 DFS에는 그런 조건 없이 먼저 이동부터 하고 봤었다. 하지만 이런 탐색은.. 전에 탐색했던 부분의 값도 넣어줘야하고 코드가 꼬인다.

그렇기 때문에 보통 BFS 사용하는 다음 목적지의 값을 확인할 수 있도록 루프 안에 조건을 넣어주었다.

class Solution {

vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};  

public:
    void dfs(int i, int j, vector<vector<bool>>& visited, vector<vector<int>>& heights){
        if(i < 0 || j < 0 || i >= heights.size() || j >= heights[0].size() || visited[i][j]) return; 
        visited[i][j] = true; 
        for(pair<int,int>& p : dir){
            int nX = i + p.first;
            int nY = j + p.second; 
            if(nX >= 0 && nY >= 0 && nX < heights.size() && nY < heights[0].size() && heights[nX][nY] >= heights[i][j]){
                dfs(nX,nY,visited,heights); 
            }
        }
    }

public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> answer; 
        vector<vector<bool>> pVisited(heights.size(), vector<bool>(heights[0].size(),false)); 
        vector<vector<bool>> aVisited(heights.size(), vector<bool>(heights[0].size(),false)); 
        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,pVisited,heights); 
                if(i == heights.size()-1 || j == heights[0].size()-1) dfs(i,j,aVisited,heights); 
            }
        }

        for(int i = 0; i < heights.size(); i++){
            for(int j = 0; j < heights[i].size(); j++){
                if(pVisited[i][j] && aVisited[i][j]) answer.push_back({i,j}); 
            }
        }

        return answer; 
    }
};