23.04.07. 풀었던 문제들

Leetcode 1020. Number of Enclaves

첫 접근

 어제 풀었던 문제와 동일한 문제. boundary에 있지 않으면서 0으로 둘러싸여 있는 1을 찾는 문제이다. 어제는 추가 공간을 할당해 모든 island의 좌표를 추가로 저장했는데, 그렇게 말고 i번째 island가 enclave인지 여부, 그리고 i번째 island에 있는 1의 개수를 저장했다.

// Runtime 87 ms Beats 30.50%
// Memory 35.1 MB Beats 14.72%

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

class Solution {
public:
    int m, n;
    vector<vector<int>> grid;
    vector<vector<bool>> visited; 
    vector<bool> isEnclave;
    vector<int> islandCount;
    void DFS(int r, int c){
        if(r == 0 || r == m-1 || c == 0 || c == n-1) isEnclave[isEnclave.size()-1] = false;
        islandCount[islandCount.size()-1]++;
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i], nc = c + dc[i];
            if(0 <= nr && nr < m && 0 <= nc && nc < n && !visited[nr][nc] && grid[nr][nc] == 1){
                visited[nr][nc] = true;
                DFS(nr, nc);
            }
        }
    }
    int numEnclaves(vector<vector<int>>& g) {
        grid = g;
        m = grid.size(); n = grid[0].size();
        vector<vector<bool>> v(m, vector<bool>(n, false));
        visited = v;

        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(!visited[i][j] && grid[i][j] == 1){
                    isEnclave.push_back(true); islandCount.push_back(0);
                    visited[i][j] = true;
                    DFS(i, j);
                }
            }
        }

        // DFS 후에는 isEnclave[i]에 해당 island의 enclave 여부, islandCount[i]에 해당 island의 1 개수가 저장된다.
        int answer = 0;
        for(int i = 0; i<isEnclave.size(); i++){
            if(isEnclave[i]) answer += islandCount[i];
        }
        return answer;
    }
};

 

 

두 번째 접근

 다른 방법을 생각하다 신박한 아이디어가 떠올랐다. 굳이 모든 island에 대해 DFS를 할 필요가 없다. boundary에 있는 모든 1인 좌표 대해 DFS를 하고, 이들을 0으로 바꿔주면, 남은 것들은 모두 boundary에 있지 않으면서 0으로 둘러싸여 있게 된다. 즉, boundary에 있는 모든 island를 0으로 바꿔주겠다는 것이다.

// Runtime 66 ms Beats 95.6%
// Memory 33 MB Beats 33.12%

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

class Solution {
public:
    int m, n;
    vector<vector<int>> grid;
    void DFS(int r, int c){
        grid[r][c] = 0;
        for(int i = 0; i<4; i++){
            int nr = r + dr[i], nc = c + dc[i];
            if(0 <= nr && nr < m && 0 <= nc && nc < n && grid[nr][nc] == 1){
                grid[nr][nc] = 0;
                DFS(nr, nc);
            }
        }
    }
    int numEnclaves(vector<vector<int>>& g) {
        grid = g;
        m = grid.size(); n = grid[0].size();

        // boundary에 DFS
        for(int i = 0; i<m; i++){
            if(grid[i][0] == 1) DFS(i, 0);
            if(grid[i][n-1] == 1) DFS(i, n-1);
        }
        for(int j = 0; j<n; j++){
            if(grid[0][j] == 1) DFS(0, j);
            if(grid[m-1][j] == 1) DFS(m-1, j);
        }

        int answer = 0;
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                answer += grid[i][j];
            }
        }
        return answer;
    }
};

 

 

시간복잡도

 DFS이므로 O(V + E), E = 4V이므로 O(V). row 길이를 m, col 길이를 n으로 했을 때 V = nm이므로 O(nm).

 

공간복잡도

 DFS이므로 worst case O(V)만큼의 스택이 쌓있다. O(nm).