23.04.06. 풀었던 문제들

Leetcode 1254. Number of Closed Islands

 많이 보던 grid에서 섬이 몇 개 있는지 탐색하는 문제이지만 추가 조건으로 모든 땅이 물 안에 있어야 하는 조건이 추가된다.

 이 문제에서는 땅이 0, 물이 1로 표현되기에 모든 0으로 표현되는 연결된 영역이 모든 1 안에 있어야 한다. 이를 판별하는 법은 0으로 연결된 영역이 grid의 테두리가 아니면 된다. grid의 테두리가 아닌 0으로 영역된 섬들은 모두 1로 둘러싸여 있기 때문이다.

• DFS로 grid[r][c]가 0인 connected island를 모두 찾는다. 찾으면서 해당 좌표를 islands에 push한다. ... 1
• DFS가 종료되면 모든 islands에 대한 정보를 찾은 것이다. islands의 모든 좌표를 순회하며 테두리에 있는지 여부를 탐색한다. 테두리에 땅이 있는 경우 1로 둘러싸여있지 않다. ... 2

// Runtime 17 ms Beats 37.16%
// Memory 11.8 MB Beats 19.3%

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

typedef pair<int, int> pii;

class Solution {
public:
    int visited[101][101];
    int maxr, maxc;
    vector<vector<int>> grid;
    vector<vector<pii>> islands;
    int cnt = 0;
    void DFS(int r, int c){ // ... 1
        for(int i = 0; i<4; i++){
            int nr = r + dr[i], nc = c + dc[i];
            if(0 <= nr && nr < maxr && 0 <= nc && nc < maxc && visited[nr][nc] == false && grid[nr][nc] == 0){
                visited[nr][nc] = true;
                islands[cnt].push_back({nr, nc});
                DFS(nr, nc);
            }
        }
    }
    int closedIsland(vector<vector<int>>& grids) {
        grid = grids;
        maxr = grid.size(); maxc = grid[0].size();
        for(int i = 0; i<maxr; i++){
            for(int j = 0; j<maxc; j++){
                visited[i][j] = false;
            }
        }
        islands.resize(1);
        
        // ... 1
        for(int i = 0; i<maxr; i++){
            for(int j = 0; j<maxc; j++){
                if(visited[i][j] == false && grid[i][j] == 0){
                    visited[i][j] = true;
                    islands[cnt].push_back({i, j});
                    DFS(i, j);
                    cnt++;
                    islands.push_back({});            
                }
            }
        }

        // ... 2
        int answer = 0;
        for(vector<pii>& island : islands){
            bool isClosed = true;
            for(pii p : island){
                if(p.first == 0 || p.first == maxr-1 || p.second == 0 || p.second == maxc-1){
                    isClosed = false;
                }
            }
            if(isClosed) answer++;
        }
        return answer-1;
    }
};

 

시간복잡도

 DFS 1번에 O(V+E), E = 4V이므로, row size를 m, col size를 n으로 표기하면 O(nm)이다. 이후 전체 좌표를 한 번 더 순회하므로 O(nm).

 

공간복잡도

 DFS를 하며 stack size는 worse case O(nm), grid와 islands vector도 O(nm)만큼 사용한다. 따라서 O(nm)