솔루션: 태평양 대서양 수류

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #417(중간): 태평양 대서양 해류

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note: The order of returned grid coordinates does not matter.
Both m and n are less than 150.

예:

Example 1:
Input:	Given the following 5x5 matrix:
Output:	[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

제약:

• Both m and n are less than 150.

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

처음부터 이 문제를 역으로 해결해야 한다는 것이 분명해야 합니다. 우리는 입력 행렬(M)의 가장자리가 각각의 측면에서 바다로 물을 흘릴 것이라는 것을 알고 있으며 인접한 셀이 현재 셀로 물을 보낼지 여부를 알 수 있으므로 가장자리부터 시작해야 합니다. 그리고 우리의 길을 안쪽으로 일하십시오.

안타깝게도 물이 이동하는 경로가 구불구불할 수 있기 때문에 일회성 반복을 수행할 수 없습니다. 대신 스택/큐 구조 또는 재귀와 함께 DFS(깊이 우선 검색) 접근 방식을 사용해야 합니다.

바다에 닿는 각 셀에 대해 우리는 대륙까지 물의 역방향 경로를 따라야 합니다. 우리는 두 대양 모두에 도달하는 셀만 원하기 때문에 반대편 바다가 잠재적으로 동일한 셀을 찾을 때까지 기다리는 동안 셀에 대한 예비 데이터를 저장할 데이터 구조가 필요합니다.

이를 수행할 수 있는 몇 가지 방법이 있지만 동적 프로그래밍(DP) 어레이(dp)를 선택하겠습니다. M의 2차원 행렬 구조를 흉내낼 실질적인 이유가 없기 때문에 대신 평면화된 1차원 배열을 사용할 수 있습니다. 그러면 약간의 처리 오버헤드가 절약됩니다. 두 대양의 데이터를 개별적으로 dp에 저장하기 위해 하나에는 +1을, 다른 하나에는 +2를 사용할 수 있습니다. 즉, 셀이 3이 되면 응답 배열(ans)에 추가해야 합니다.

DFS 재귀 함수(dfs)는 또한 비트 AND(&) 연산자를 사용하여 이 셀에 현재 바다(w)를 표시하지 않았는지 확인해야 합니다. 그런 다음 dfs의 끝에서 가능하면 네 방향 모두에서 새로운 재귀를 시작해야 합니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var pacificAtlantic = function(M) {
    if (!M.length) return M
    let y = M.length, x = M[0].length, ans = [],
        dp = new Uint8Array(x * y)
    const dfs = (i, j, w, h) => {
        let ij = i * x + j
        if ((dp[ij] & w) || M[i][j] < h) return
        dp[ij] += w, h = M[i][j]
        if (dp[ij] === 3) ans.push([i,j])
        if (i + 1 < y) dfs(i+1, j, w, h)
        if (i > 0) dfs(i-1, j, w, h)
        if (j + 1 < x) dfs(i, j+1, w, h)
        if (j > 0) dfs(i, j-1, w, h)
    }   
    for (let i = 0; i < y; i++) {
        dfs(i, 0, 1, M[i][0])
        dfs(i, x-1, 2, M[i][x-1])
    }
    for (let j = 0; j < x; j++) {
        dfs(0, j, 1, M[0][j])
        dfs(y-1, j, 2, M[y-1][j])
    }
    return ans
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def pacificAtlantic(self, M: List[List[int]]) -> List[List[int]]:
        if not M: return M
        x, y = len(M[0]), len(M)
        ans, dp = [], [0] * (x * y)
        def dfs(i: int, j: int, w: int, h: int):
            ij = i * x + j
            if dp[ij] & w or M[i][j] < h: return
            dp[ij] += w
            h = M[i][j]
            if dp[ij] == 3: ans.append([i,j])
            if i + 1 < y: dfs(i+1, j, w, h)
            if i > 0: dfs(i-1, j, w, h)
            if j + 1 < x: dfs(i, j+1, w, h)
            if j > 0: dfs(i, j-1, w, h)
        for i in range(y):
            dfs(i, 0, 1, M[i][0])
            dfs(i, x-1, 2, M[i][x-1])
        for j in range(x):
            dfs(0, j, 1, M[0][j])
            dfs(y-1, j, 2, M[y-1][j])
        return ans

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    static void dfs(int i, int j, int w, int h, int[][] M, byte[] dp, List<List<Integer>> ans) {
        int ij = i * M[0].length + j;
        if ((dp[ij] & w) > 0 || M[i][j] < h) return;
        dp[ij] += w;
        h = M[i][j];
        if (dp[ij] == 3) ans.add(Arrays.asList(i,j));
        if (i + 1 < M.length) dfs(i+1, j, w, h, M, dp, ans);
        if (i > 0) dfs(i-1, j, w, h, M, dp, ans);
        if (j + 1 < M[0].length) dfs(i, j+1, w, h, M, dp, ans);
        if (j > 0) dfs(i, j-1, w, h, M, dp, ans);
    }
    public List<List<Integer>> pacificAtlantic(int[][] M) {
        List<List<Integer>> ans = new ArrayList<>();
        if (M.length == 0) return ans;
        int y = M.length, x = M[0].length;
        byte[] dp = new byte[x * y];
        for (int i = 0; i < x; i++) {
            dfs(0, i, 1, M[0][i], M, dp, ans);
            dfs(y-1, i, 2, M[y-1][i], M, dp, ans);
        }   
        for (int i = 0; i < y; i++) {
            dfs(i, 0, 1, M[i][0], M, dp, ans);
            dfs(i, x-1, 2, M[i][x-1], M, dp, ans);
        }
        return ans;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& M) {
        vector<vector<int>> ans;
        if (M.empty()) return ans;
        int y = M.size(), x = M[0].size();
        vector<char> dp(y * x);
        for (int i = 0; i < y; i++) {
            dfs(M, dp, i, 0, 1, 0);
            dfs(M, dp, i, x - 1, 2, 0);
        }
        for (int i = 0; i < x; i++) {
            dfs(M, dp, 0, i, 1, 0);
            dfs(M, dp, y - 1, i, 2, 0);
        }
        for (int i = 0; i < y; i++) 
            for (int j = 0; j < x; j++) 
                if (dp[i * x + j] == 3) 
                    ans.push_back({i, j});
        return ans;
    }
private:
    void dfs(const vector<vector<int>>& M, vector<char>& dp, int i, int j, int w, int h) {
        int y = M.size(), x = M[0].size(), ij = i * x + j, newh = M[i][j];;
        if ((dp[ij] & w) || M[i][j] < h) return;
        dp[ij] += w;
        if (i + 1 < y) dfs(M, dp, i + 1, j, w, newh);
        if (i > 0) dfs(M, dp, i - 1, j, w, newh);
        if (j + 1 < x) dfs(M, dp, i, j + 1, w, newh);
        if (j > 0) dfs(M, dp, i, j - 1, w, newh);
    }
};