23.04.30. 풀었던 문제들

Leetcode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

 어제 문제를 풀었다면 접근을 조금 쉽게 할 수 있는 문제. 문제 힌트에도 대놓고 [graph를 완성한 후 비교하는 것이 아니라, 거꾸로 생각해라] => [0부터 build해나가는 식으로 만들어라] => 즉, union-find를 이용해 graph를 이어나가면 된다.

 

 A와 B 각각의 edge를 union-find를 이용해 graph를 만들어가는 방법을 생각했다. 단 주의해야 할 부분으로

• A, B로만 edge를 만들고 common edge 중 없앨 수 있는 edge만 없앨지
• common edge로 기본 graph를 만들고, A, B edge 중 사용해야 하는 것만 사용하고 나머지는 버릴지

가 중요하다. 직관적으로 생각해 보면 common edge는 A와 B 모두에서 edge로 작동하므로 가능하다면 포함하는 것이 좋을 것이다. 따라서 아래 방법을 사용하는 것이 더 많은 [필요없는 edge]를 만들 수 있을 것이다.

 

 또한, 문제에서 A 또는 B가 graph를 연결할 수 없는 edges가 주어진 경우 -1을 리턴하라고 한다. tree의 성질(edge는 n-1개, 모든 vertex conntected)을 이용해 정확하게 n-1개의 edge를 사용하면 graph vertex n개를 모두 연결할 수 있다는 것을 알 수 있다. 따라서 union을 할 때(edge를 graph에 편입시킬 때) 몇 개의 edge를 사용했는지 count를 해 주면 된다.

 

 union-find의 특성을 이용해 두 edge가 이미 연결되었는지 아닌지는 해당 vertex root를 비교하는 것으로 쉽게 찾을 수 있다. 연결되지 않았다면 union하고 [연결한 edge 개수]++ 해 준다. 연결되었다면 [필요없는 edge 개수]++해 준다.

 

// Runtime 717 ms Beats 39.49%
// Memory 139 MB Beats 82.61%

// union-find class
class DSU{
public:
    vector<int> rank, parent;
    DSU(int n){
        rank.resize(n, 0);
        parent.resize(n);
        for(int i = 0; i<n; i++){
            parent[i] = i;
        }
    }

    int find(int x){
        if(x == parent[x]) return x;
        parent[x] = find(parent[x]);
        return parent[x];
    }

    void join(int x, int y){
        int rx = find(x), ry = find(y);
        if(rank[rx] > rank[ry]){ // ry가 아래로 들어가야 함
            parent[ry] = rx;
        }
        else{
            parent[rx] = ry;
            if(rank[rx] == rank[ry]) rank[ry]++;
        }
    }

    bool isConnected(int x, int y){
        return find(x) == find(y);
    }
};

bool cmp(vector<int>& a, vector<int>& b){
    return a[0] > b[0];
}

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        DSU groupA = DSU(n+1), groupB = DSU(n+1);
        sort(edges.begin(), edges.end(), cmp); // *** common edge부터 시작해야 함
        int answer = 0, numAEdges = 0, numBEdges = 0;
        for(vector<int>& edge : edges){
            int type = edge[0], x = edge[1], y = edge[2];
            bool isAConnected = groupA.isConnected(x, y), isBConnected = groupB.isConnected(x, y);

            if(type == 3){
                if(isAConnected && isBConnected){ // 이미 연결되었다면 필요없는 edge
                    answer++;
                }
                if(!isAConnected){ // 연결되지 않았다면 edge개수++, union으로 연결시킴
                    numAEdges++;
                    groupA.join(x, y);
                }
                if(!isBConnected){ // 이하동문
                    numBEdges++;
                    groupB.join(x, y);
                }
            }
            else if(type == 1){
                if(isAConnected) answer++;
                else numAEdges++;
                groupA.join(x, y);
            }
            else if(type == 2){
                if(isBConnected) answer++;
                else numBEdges++;
                groupB.join(x, y);
            }
        }

        if(numAEdges != n-1 || numBEdges != n-1) return -1; // *** edge 개수가 n-1개가 아니면 연결되지 않은 것
        return answer;
    }
};

 

시간복잡도

 union-find에서 각 operation은 O(log*n). 이 문제의 vertex는 n개, edges size를 E라고 하자. 그러면 for문에서 E번 순회하므로 O(E), 각 순회에서 find, union을 하므로 O(Elog*n)이다.

 

공간복잡도

 union-find class를 2개 사용하므로 O(n)이다.