[LeetCode] 1568. Minimum Number of Days to Disconnect Island

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/description/

leetcode - Minimum Number of Days to Disconnect Island

문제 유형 : bfs / dfs, 그리디

문제 난이도 : Hard

 

문제

You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we are allowed to change any single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

 

풀이

값의 범위가 0 ~ 2임을 알 수 있다.

0 - 섬이 애초에 1개가 아닌, 즉 0개 또는 2개이상인 경우

1 - 
1 1 0 1 1      1 1 0 1 1

1 1 1 1 1 -> 1 1 0 1 1

1 1 0 1 1      1 1 0 1 1

에서의 경우와 같이 다리를 잇는 경우이거나, 

1 0 0 0 0      1 0 0 0 0

1 1 0 0 0 -> 0 1 0 0 0

1 1  1  1 1      1  1 1  1 1

과 같은 벼량에 있는 땅을 분리하는 꼴일 것이다.

 

2 - 맨 끝의 요소를

1 1 1 1 1      1 0 1 1 1

1 1 1 1 1 -> 0 1 1 1 1

과 같이 맨 끄트머리를 분할하는 경우이다.

 

섬의 개수와 넓이를 구하는 함수를 만들어서, 섬의 개수와 넓이를 파악하는데, 처음에 구할 때에는, 섬이 한 개이고, 그 넓이가 2인 경우라면, 이는 특이 케이스로 정답이 2이다.

1 1 인경우, 0 0 이어야 하기 때문이다.

 

이 경우를 제외하고는, 각 셀을 제거하거나 각 셀을 다른 셀들로부터 분리키시는 방식으로 최소값을 구해낸다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    int m, n;
public:
    vector<int> traverse(vector<vector<int>> &grid) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<int> res;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] && !visited[i][j]) {
                    if(res.size() == 1) {
                        res.push_back(1);
                        return res;
                    }
                    int size = 1;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    visited[i][j] = true;
                    while(!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();

                        for(int k = 0; k < 4; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                            if(!grid[nx][ny]) continue;
                            if(visited[nx][ny]) continue;
                            
                            q.push({nx, ny});
                            visited[nx][ny] = true;
                            size++;
                        }
                    }
                    res.push_back(size);
                }
            }
        }
        return res;
    }
    int minDays(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<int> islands = traverse(grid);

        if(islands.size() != 1) return 0;
        if(islands.size() == 1 && islands[0] == 1) return 1;
        if(islands.size() == 1 && islands[0] == 2) return 2;

        int ans = INT_MAX;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    int change = 0;
                    for(int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                            change++;
                        }
                    }
                    ans = min(ans, change);

                    grid[i][j] = 0;
                    auto islandsWithPunch = traverse(grid);
                    grid[i][j] = 1;
                    if(islandsWithPunch.size() != 1) return 1;
                }
            }
        }

        return ans;
    }
};