417. Pacific Atlantic Water Flow

1. 모든 셀에 대해 pacific & atlantic 확인하기 : 직관적 / 복잡한 구현.

class Solution {
public:
    vector<vector<int>> mem;
    
    int f(vector<vector<int>>& H, int r, int c, bool direct=true) {
        int n = H.size(), m = H[0].size();
        if (r == 0 || c == 0) mem[r][c] |= 1;
        if (r == n - 1 || c == m - 1) mem[r][c] |= 2;
        if ((mem[r][c] & 3) == 3) return 3;
        mem[r][c] ^= 4;
        if (direct) mem[r][c] |= 8;
        
        int dir[] = {-1, 0, 1, 0, -1};
        for (int i = 0; i < 4; ++i) {
            int nr = r + dir[i];
            int nc = c + dir[i + 1];
            if (nr < 0 || n <= nr || nc < 0 || m <= nc) continue;
            if (H[r][c] < H[nr][nc]) continue;
            if (direct && (mem[nr][nc] & 8) == 8) mem[r][c] |= mem[nr][nc];
            else if ((mem[nr][nc] & 4) == 4) continue;
            else mem[r][c] |= f(H, nr, nc, false);
            if ((mem[r][c] & 3) == 3) break;
        }
        mem[r][c] ^= 4;
        return mem[r][c];
    }
    
    
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& H) {
        int n = H.size();
        int m = H[0].size();
        mem.resize(n, vector<int>(m, 0));
        
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if ((f(H, i, j) & 3) == 3)
                    ans.push_back({i, j});
            }
        }
        
        return ans;
    }
};

---

2. 역으로 접근. 불필요한 순회를 하지 않기에 빠름.

class Solution {
public:
    void dfs(vector<vector<int>>& H, vector<vector<int>>& ocean, int r, int c) {
        int n = H.size(), m = H[0].size();
        ocean[r][c] = 1;
        
        int dir[] = {-1, 0, 1, 0, -1};
        for (int i = 0; i < 4; ++i) {
            int nr = r + dir[i];
            int nc = c + dir[i + 1];
            
            if (nr < 0 || n <= nr || nc < 0 || m <= nc) continue;
            if (H[nr][nc] < H[r][c]) continue;
            if (ocean[nr][nc] == 1) continue;
            dfs(H, ocean, nr, nc);
        }
    }
    
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& H) {
        int n = H.size(), m = H[0].size();
        vector<vector<int>> Ps(n, vector<int>(m, 0));
        vector<vector<int>> As(n, vector<int>(m, 0));
        
        for (int i = 0; i < n; ++i) {
            dfs(H, Ps, i, 0);
            dfs(H, As, i, m - 1);
        }
        
        for (int i = 0; i < m; ++i) {
            dfs(H, Ps, 0, i);
            dfs(H, As, n - 1, i);
        }
        
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (Ps[i][j] == 1 && As[i][j] == 1) 
                    ans.push_back({i, j});
            }
        }
        return ans;
    }
};