[ leetcode 문제풀이 ] Pacific Atlantic Water Flow

Pacific Atlantic Water Flow - LeetCode

Pacific Atlantic Water Flow - LeetCode

(Pacific Atlantic Water Flow 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Pacific Atlantic Water Flow 문제 설명 >

 

Pacific Atlantic Water Flow 문제는 다음과 같다.

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

 

태평양과 대서양을 경계로 한 m x n 직사각형 섬이 있다. 태평양은 섬의 왼쪽과 위쪽 가장자리에 닿고, 대서양은 섬의 오른쪽과 아래쪽 가장자리에 닿는다.

m x n 정수 행렬 높이가 주어지며, 여기서 heights[r][c]는 좌표(r, c)에서 셀의 해수면 위 높이를 나타낸다. 섬에는 많은 비가 내리는데, 이웃 cell의 높이가 현재 cell의 높이보다 작거나 같으면 빗물이 바로 북쪽, 남쪽, 동쪽, 서쪽으로 이웃 셀로 흐를 수 있다. 바다에 인접한 어떤 cell에서도 바다로 물이 흐를 수 있다.
태평양과 대서양 모두로 물이 흐를 수 있는 좌표를 나타내는 2차원 리스트 result를 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 m == heights.length,  n == heights[r].length,  1 ≤ m,n ≤ 200,  0 ≤ heights[r][c] ≤ 10^5 이다.

 

 

 

 

---

< Pacific Atlantic Water Flow 문제 접근(실패 ver.) >

 

임의의 위치 [row, col]에서 Pacific Ocean과 Atlantic Ocean에 도달할 수 있는지 여부를 판별하기 위해서는 [row, col]에서 출발해 이동할 수 있는 경로를 탐색해 Pacific, Atlantic Ocean에 도달하는지를 확인하면 될 것이다. 

 

그러기 위해 1)이동할 수 있는 경로를 Graph로 만들고 2) grid의 모든 cell([row, col])에 대해 Pacific, Atlantic Ocean에 도달하는지를 확인하기 위해 Graph를 탐색하며 3)두 경우를 모두 만족하는 cell을 2D list에 저장해 리턴 의 과정으로 코드를 구현하고자 하였다. 아래 코드를 살펴보자. (Cpp 사용)

 

typedef vector<vector<int>> point;
struct cellInfo{
    int canPacific = -1; // no Info
    int canAtlantic = -1; // no Info
    point canGo;
};
    
void makeGraph(cellInfo** GridInfo, point& heights, int row, int col){
    if(col > 0 && heights[row][col] >= heights[row][col-1])
        GridInfo[row][col].canGo.push_back({row, col-1});
    if(col < heights[row].size()-1 && heights[row][col] >= heights[row][col+1])
        GridInfo[row][col].canGo.push_back({row, col+1});
    if(row > 0 && heights[row][col] >= heights[row-1][col])
        GridInfo[row][col].canGo.push_back({row-1, col});
    if(row < heights.size()-1 && heights[row][col] >= heights[row+1][col])
        GridInfo[row][col].canGo.push_back({row+1, col});
}    
    
void findWay_Pac(cellInfo** GridInfo, point& heights, int row, int col){
    if(GridInfo[row][col].canPacific != -1)
        return; // memoization이 true or false 로 되어있으면 리턴.
        
    GridInfo[row][col].canPacific = 0;
      
    for(vector<int> cell_cango : GridInfo[row][col].canGo){
        findWay_Pac(GridInfo, heights, cell_cango[0], cell_cango[1]);
        if(GridInfo[cell_cango[0]][cell_cango[1]].canPacific){
            GridInfo[row][col].canPacific = 1;
            break;
        }
    }
}
    
void findWay_Atl(cellInfo** GridInfo, point& heights, int row, int col){
    if(GridInfo[row][col].canAtlantic != -1)
        return; // memoization이 true or false 로 되어있으면 리턴.
        
    GridInfo[row][col].canAtlantic = 0;
      
    for(vector<int> cell_cango : GridInfo[row][col].canGo){
        findWay_Atl(GridInfo, heights, cell_cango[0], cell_cango[1]);
        if(GridInfo[cell_cango[0]][cell_cango[1]].canAtlantic){
            GridInfo[row][col].canAtlantic = 1;
            break;
        }
    }
}     
    
vector<vector<int>> pacificAtlantic(point& heights) {
    int m = heights.size(), n = heights[0].size();
    cellInfo** GridInfo = new struct cellInfo*[m];
    for(int i=0;i<m;i++)
        GridInfo[i] = new struct cellInfo[n];
        
    // 테두리 정보 입력
    for(int row=0;row<m;row++){
        GridInfo[row][0].canPacific = 1;
        GridInfo[row][n-1].canAtlantic = 1;
    }
    for(int col=0;col<n;col++){
        GridInfo[0][col].canPacific = 1;
        GridInfo[m-1][col].canAtlantic = 1;
    }        
        
    // water flow의 graph 생성
    for(int row=0;row<m;row++)
        for(int col=0;col<n;col++)
            makeGraph(GridInfo, heights, row, col);
        
    // findWay_Pac, findWay_Atl 삽입 부분 
    for(int row=0;row<m;row++)
        for(int col=0;col<n;col++){
            findWay_Pac(GridInfo, heights, row, col);
            findWay_Atl(GridInfo, heights, row, col);
        }
        
    point ans;
    for(int row=0;row<m;row++)
        for(int col=0;col<n;col++)
            if(GridInfo[row][col].canPacific && GridInfo[row][col].canAtlantic)
                ans.push_back({row, col});
                  
    return ans;
}

 

cellInfo라는 구조체는 grid의 cell에 대해 Pacific, Atlantic Ocean에 도달할 수 있는지 여부를 저장하는 canPacific, canAtlantic과 물이 흐를 수 있는 인접 cell의 위치를 저장하는 canGo를 가지고 있다.

 

makeGraph 함수는 현재 cell([row, col])의 높이와 같거나 작은 높이의 인접 cell을 GridInfo[row][col].canGo에 저장한다.

findWay_Pac과 findWay_Atl 함수는 현재 cell([row, col])에서 canGo의 인접 cell로 구성된 Graph를 DFS로 탐색하며 canPacific과 canAltantic을 업데이트한다. 이때 이미 알고있는 섬 테두리의 canPacific과 canAtlantic 정보는 미리 초기화한다.

 

DFS가 끝나고 각 cell에 대한 canPacific과 canAtlantic 여부를 확인해 답을 출력한다.

 

 

그러나 이렇게 구성한 코드는 다음과 같이 잘못된 답을 출력했다.

 

문제가 된 [35, 3] cell은 인접한 [35, 2]를 통한 경로로만 Pacific, Atlantic Ocean에 도달할 수 있었는데 이 두 cell의 높이가 같아 탐색 과정의 문제가 발생하였다. findWay 함수에서 memoization여부를 확인한 후 GridInfo[row][col].canPacific or .canAtlantic  = 0 으로 초기화 한 것이 문제였는데, 프로그램이 실행된 과정을 살펴보면

[35,2]에 대한 탐색 시작 → [35,2].canPacific = 0 초기화 → findWay([35,3]) 호출 → [35,3].canPacific = 0 초기화 → findWay([35,2]) 호출 → [35,2].canPacific != -1 이므로 findWay([35,3])종료 → ... 이므로 [35,3]에 대한 탐색을 진행하려고 하면 앞서 [35,3].canPacific = 0으로 초기화해뒀기 때문에 [35,2]를 통한 경로를 탐색하지 못하게 된다. 

 

물론 그렇다고 GridInfo[row][col].canPacific or canAtlantic = 0 초기화를 for문 뒤에 두게 되면 인접한 두 cell에 대한 탐색이 반복되어 호출되는 무한 loop에 빠지게 되므로 할 수 없었다.

 

 

이걸 해결하기 위해선 같은 높이를 가진 인접한 cell에 대해서는 한 번에 한 방향으로만 탐색이 가능하도록 처리를 해줘야 했다. 말...은 쉽지만 이걸 직접 구현한다고 생각하면 canGo에서 같은 높이를 갖는 인접 cell은 따로 분류하고, findWay 함수도 같은 높이의 인접 cell에 대한 탐색을 고려하도록 설계해야하므로 너무 복잡해진다. 

 

그래서 아에 새로운 방법으로 탐색하기로 했다. 

 

 

 

---

< Pacific Atlantic Water Flow 문제 접근(성공 ver.) >

 

실패한 버전에서는 현재 cell에서 섬의 edge cell까지 도달할 수 있는지를 살펴보는 일종의 top-down approach를 사용하였다. 그래서 이번엔 bottom-up approach로 접근해보았다. Pacific or Atlantic Ocean과 닿아있는 edge cell 에서 출발해 도달할 수 있는 cell에 대해 canPacific, canAtlantic을 true로 저장하는 것이다. 이 방법을 사용하면 같은 높이의 인접 cell이 있다고 하더라도 문제가 되지 않는다. 구체적으로 작성한 코드는 다음과 같다. (Cpp 사용)

 

vector<vector<int>> direction = {{-1,0}, {1,0}, {0,1}, {0,-1}};
void findWay(vector<vector<int>>& heights, vector<vector<bool>>& visited, int row, int col, int m, int n){
    if(visited[row][col]) return;
    visited[row][col] = true;
        
    for(auto way : direction){
        int y = row + way[0], x = col + way[1];
        if(y<0 || y>=m || x<0 || x>=n || heights[row][col] > heights[y][x])
            continue;
        findWay(heights, visited, y, x, m, n);
        }
    }
   
 vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<bool>> canPacific(m, vector<bool>(n));
    vector<vector<bool>> canAtlantic(m, vector<bool>(n));
        
    // findWay(DFS)
    for(int row=0;row<m;row++){
        findWay(heights, canPacific, row, 0, m, n);
        findWay(heights, canAtlantic, row, n-1, m, n);
    }
    for(int col=0;col<n;col++){
        findWay(heights, canPacific, 0, col, m, n);
        findWay(heights, canAtlantic, m-1, col, m, n);
    }
        
    vector<vector<int>> ans;
    for(int row=0;row<m;row++)
        for(int col=0;col<n;col++)
            if(canPacific[row][col] && canAtlantic[row][col])
                ans.push_back({row, col});
                    
    return ans;
}

 

확실히 bottom-up approach를 사용하고 나니 훨씬 간단해졌다. 

 

이 문제처럼 end 조건(canPacific, canAtlantic is true)가 특정 cell로 정해져 있는 경우 등은 bottom-up approach를 사용하는 것이 적합해보인다. (top-down approach로 출발하는 것이 더 직관적이지만 알고리즘을 구현하고 나서 살펴보면 bottom-up이 간결하고 효율적인 코드를 내는 것 같다.)